Computing isolated roots of sparse polynomial systems in affine space

DOI10.1016/j.tcs.2010.07.015zbMath1241.65046OpenAlexW1968693041MaRDI QIDQ410703

Gabriela Jeronimo, María Isabel Herrero, Juan Sabia

Publication date: 3 April 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.07.015

zbMATH Keywords

complexityalgorithmsprobabilistic algorithmcoding theorysparse systemsAffineSolveisolated common zerospolyhedral deformationssparse polynomial systems

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Numerical computation of solutions to systems of equations (65H10) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Complexity of computation (including implicit computational complexity) (03D15) Complexity and performance of numerical algorithms (65Y20) Numerical computation of roots of polynomial equations (65H04)

Related Items

Solving determinantal systems using homotopy techniques, Homotopy techniques for solving sparse column support determinantal polynomial systems, Elimination for generic sparse polynomial systems, On the multiplicity of isolated roots of sparse polynomial systems, 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
• Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
• Bernstein's theorem in affine space
• Dynamic enumeration of all mixed cells
• Deformation techniques for sparse systems
• 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
• A convex geometric approach to counting the roots of a polynomial system
• Straight-line programs in geometric elimination theory
• Mixed volume computation for semi-mixed systems
• 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
• Deformation techniques for efficient polynomial equation solving.
• Counting affine roots of polynomial systems via pointed Newton polytopes
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• The BKK root count in $\mathbf {C}^n$
• A Polyhedral Method for Solving Sparse Polynomial Systems
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Algorithms in real algebraic geometry
• A Gröbner free alternative for polynomial system solving
• Finding mixed cells in the mixed volume computation