Deformation techniques for sparse systems

DOI10.1007/S10208-008-9024-2MaRDI QIDQ1029552zbMATH OpenOpenAlexFDO

Authors Gabriela Jeronimo, Guillermo Matera, Pablo Solernó, Ariel Waissbein

Publication date 13 July 2009

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Formal power series rings (13F25) Computational aspects of algebraic curves (14Q05) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Abstract: We exhibit a probabilistic symbolic algorithm for solving zero-dimensional sparse systems. Our algorithm combines a symbolic homotopy procedure, based on a flat deformation of a certain morphism of affine varieties, with the polyhedral deformation of Huber and Sturmfels. The complexity of our algorithm is quadratic in the size of the combinatorial structure of the input system. This size is mainly represented by the mixed volume of Newton polytopes of the input polynomials and an arithmetic analogue of the mixed volume associated to the deformations under consideration.

Recommendations

• Computing isolated roots of sparse polynomial systems in affine space
• Affine solution sets of sparse polynomial systems
• Deformation techniques to solve generalised Pham systems
• Elimination for generic sparse polynomial systems
• Deformation techniques for efficient polynomial equation solving.

Cites work

• scientific article; zbMATH DE number 47206 (Why is no real title available?)
• scientific article; zbMATH DE number 50337 (Why is no real title available?)
• scientific article; zbMATH DE number 1273538 (Why is no real title available?)
• scientific article; zbMATH DE number 481965 (Why is no real title available?)
• scientific article; zbMATH DE number 575960 (Why is no real title available?)
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1033441 (Why is no real title available?)
• scientific article; zbMATH DE number 1057737 (Why is no real title available?)
• scientific article; zbMATH DE number 1069614 (Why is no real title available?)
• scientific article; zbMATH DE number 1142301 (Why is no real title available?)
• scientific article; zbMATH DE number 2051430 (Why is no real title available?)
• scientific article; zbMATH DE number 2151179 (Why is no real title available?)
• scientific article; zbMATH DE number 939802 (Why is no real title available?)
• scientific article; zbMATH DE number 3999284 (Why is no real title available?)
• scientific article; zbMATH DE number 960150 (Why is no real title available?)
• scientific article; zbMATH DE number 3059981 (Why is no real title available?)
• A Gröbner free alternative for polynomial system solving
• A Polyhedral Method for Solving Sparse Polynomial Systems
• A Product-Decomposition Bound for Bezout Numbers
• A concise proof of the Kronecker polynomial system solver from scratch
• Bernstein's theorem in affine space
• Bounds of traces in complete intersections and degrees in the Nullstellensatz
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Computing parametric geometric resolutions
• Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
• Counting affine roots of polynomial systems via pointed Newton polytopes
• Deformation techniques for efficient polynomial equation solving.
• Deformation techniques to solve generalised Pham systems
• Diophantine geometry and toric varieties.
• Efficient incremental algorithms for the sparse resultant and the mixed volume
• Finding mixed cells in the mixed volume computation
• High probability analysis of the condition number of sparse polynomial systems
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• Lower bounds for diophantine approximations
• Mixed-volume computation by dynamic lifting applied to polynomial system solving
• Modern computer algebra
• Newton polyhedra and the genus of complete intersections
• Newton polytopes and the Bezout theorem
• Polynomial equation solving by lifting procedures for ramified fibers
• Polynomial evaluation and interpolation on special sets of points
• Product formulas for resultants and Chow forms
• Quadratic Newton iteration for systems with multiplicity
• Solving degenerate sparse polynomial systems faster
• Straight-line programs in geometric elimination theory
• The BKK root count in $\mathbf {C}^n$
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• The complexity of partial derivatives
• The computational complexity of the Chow form
• The hardness of polynomial equation solving
• The number of roots of a system of equations

Cited in

(26)

• A package for computations with sparse resultants
• Solving determinantal systems using homotopy techniques
• Symbolic computation in hyperbolic programming
• A concise proof of the Kronecker polynomial system solver from scratch
• Computing isolated roots of sparse polynomial systems in affine space
• Locating the closest singularity in a polynomial homotopy
• On the bit complexity of polynomial system solving
• Tropical algebraic geometry in Maple: a preprocessing algorithm for finding common factors for multivariate polynomials with approximate coefficients
• The method of Gauss-Newton to compute power series solutions of polynomial homotopies
• Solving rank-constrained semidefinite programs in exact arithmetic
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• A Poisson formula for the sparse resultant
• Computing critical points for invariant algebraic systems
• Computing all space curve solutions of polynomial systems by polyhedral methods
• A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
• On sign conditions over real multivariate polynomials
• Elimination for generic sparse polynomial systems
• Exact algorithms for linear matrix inequalities
• Solving decomposable sparse systems
• Sparse resultants and straight-line programs
• The Canny-Emiris conjecture for the sparse resultant
• Deformation techniques to solve generalised Pham systems
• A robust numerical path tracking algorithm for polynomial homotopy continuation
• Real root finding for low rank linear matrices
• The persistent homology of dual digital image constructions
• Homotopy techniques for solving sparse column support determinantal polynomial systems

Describes a project that uses

Uses Software

• Kronecker

This page was built for publication: Deformation techniques for sparse systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1029552)