On the complexity exponent of polynomial system solving
From MaRDI portal
Publication:2658549
DOI10.1007/s10208-020-09453-0zbMath1457.14002OpenAlexW2950049430MaRDI QIDQ2658549
Joris van der Hoeven, Grégoire Lecerf
Publication date: 23 March 2021
Published in: Foundations of Computational Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10208-020-09453-0
Symbolic computation and algebraic computation (68W30) Singularities in algebraic geometry (14B05) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Software, source code, etc. for problems pertaining to algebraic geometry (14-04)
Related Items
Computing Riemann-Roch spaces via Puiseux expansions, Elimination ideal and bivariate resultant over finite fields, On the computation of rational solutions of underdetermined systems over a finite field, Segre-driven radicality testing, Fast amortized multi-point evaluation, Amortized multi-point evaluation of multivariate polynomials
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deterministic root finding over finite fields using Graeffe transforms
- Relaxed algorithms for \(p\)-adic numbers
- Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
- Modular composition via factorization
- On computing the determinant in small parallel time using a small number of processors
- Definability and fast quantifier elimination in algebraically closed fields
- Sur des hauteurs alternatives. I. (On alternative heights. I)
- Bounds for the degrees in the Nullstellensatz
- On fast multiplication of polynomials over arbitrary algebras
- Fast rectangular matrix multiplication and applications
- Efficient computation of zero-dimensional Gröbner bases by change of ordering
- Mahler measure and computation of universal constants for polynomials in \(n\) variables
- Lower bounds for diophantine approximations
- Straight-line programs in geometric elimination theory
- Effective equidimensional decomposition of affine varieties
- Fast computation of isomorphisms between finite fields using elliptic curves
- On the bit complexity of polynomial system solving
- On the complexity of the Lickteig-Roy subresultant algorithm
- PRIMES is in P
- Sharp estimates for the arithmetic Nullstellensatz
- On the complexity of computing with zero-dimensional triangular sets
- Numerical methods for roots of polynomials. II
- Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
- Fast multivariate multi-point evaluation revisited
- Accelerated tower arithmetic
- Degeneracy loci and polynomial equation solving
- On the complexity of the \(F_5\) Gröbner basis algorithm
- Polynomial evaluation and interpolation on special sets of points
- A concise proof of the Kronecker polynomial system solver from scratch
- Polynomial root finding over local rings and application to error correcting codes
- Fast computation of special resultants
- Fast computation of continued fraction expansions.
- Modern Computer Algebra
- Fast Polynomial Factorization and Modular Composition
- Sub-cubic change of ordering for Gröbner basis
- Powers of tensors and fast matrix multiplication
- Solving projective complete intersection faster
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Fast Algorithms for Manipulating Formal Power Series
- Reductions modulo primes of systems of polynomial equations and algebraic dynamical systems
- Faster integer multiplication using plain vanilla FFT primes
- Accelerated Solution of Multivariate Polynomial Systems of Equations
- Composition Modulo Powers of Polynomials
- Border basis representation of a general quotient algebra
- Generalized normal forms and polynomial system solving
- Fast construction of irreducible polynomials over finite fields
- A Gröbner free alternative for polynomial system solving
