Elimination for generic sparse polynomial systems

DOI10.1007/s00454-014-9571-zzbMath1310.68261arXiv1303.0266OpenAlexW2963839416MaRDI QIDQ2249474

María Isabel Herrero, Gabriela Jeronimo, Juan Sabia

Publication date: 1 July 2014

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1303.0266

zbMATH Keywords

computational complexitysparse polynomial systemsprobabilistic symbolic algorithmprojection of algebraic varieties

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational aspects of higher-dimensional varieties (14Q15) Polynomials in general fields (irreducibility, etc.) (12E05) Numerical linear algebra (65F99) Solving polynomial systems; resultants (13P15)

Related Items

Solving determinantal systems using homotopy techniques, Homotopy techniques for solving sparse column support determinantal polynomial systems, Computing All Space Curve Solutions of Polynomial Systems by Polyhedral Methods, Computing critical points for invariant algebraic systems

Uses Software

• DEMiCs
• Kronecker

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing isolated roots of sparse polynomial systems in affine space
• Bernstein's theorem in affine space
• A geometric index reduction method for implicit systems of differential algebraic equations
• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• On computing the determinant in small parallel time using a small number of processors
• Definability and fast quantifier elimination in algebraically closed fields
• How to compute the Chow form of an unmixed polynomial ideal in single exponential time
• Dynamic enumeration of all mixed cells
• Deformation techniques for sparse systems
• Mixed volume techniques for embeddings of Laman graphs
• Newton polyhedra and toroidal varieties
• The number of roots of a system of equations
• Newton polytopes and the Bezout theorem
• How to count efficiently all affine roots of a polynomial system
• An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs
• On the Newton polytope of the resultant
• A convex geometric approach to counting the roots of a polynomial system
• Mixed volume computation for semi-mixed systems
• Computing parametric geometric resolutions
• Finding all isolated zeros of polynomial systems in \(\mathbb{C}^n\) via stable mixed volumes
• The computational complexity of the Chow form
• Efficient incremental algorithms for the sparse resultant and the mixed volume
• Mixed-volume computation by dynamic lifting applied to polynomial system solving
• Affine solution sets of sparse polynomial systems
• Computing multihomogeneous resultants using straight-line programs
• Counting affine roots of polynomial systems via pointed Newton polytopes
• Macaulay style formulas for sparse resultants
• Polyhedral Methods in Numerical Algebraic Geometry
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• On The Complexity of Computing Mixed Volumes
• The BKK root count in $\mathbf {C}^n$
• A Polyhedral Method for Solving Sparse Polynomial Systems
• Polyhedral Methods for Space Curves Exploiting Symmetry Applied to the Cyclic n-roots Problem
• Computing Puiseux series for algebraic surfaces
• A subdivision-based algorithm for the sparse resultant
• A Gröbner free alternative for polynomial system solving
• Finding mixed cells in the mixed volume computation
• Explicit formulas for the multivariate resultant.