Computing isolated roots of sparse polynomial systems in affine space
AffineSolvealgorithmscoding theorycomplexityisolated common zerospolyhedral deformationsprobabilistic algorithmsparse polynomial systemssparse systems
Complexity of computation (including implicit computational complexity) (03D15) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Numerical computation of roots of polynomial equations (65H04) Numerical computation of solutions to systems of equations (65H10) Complexity and performance of numerical algorithms (65Y20) Symbolic computation and algebraic computation (68W30)
The subject of this paper concerns solving -- numerically and symbolically -- polynomial equation systems over \(\mathbb{C}^*\). Because actual efficient algorithms are based on the polyhedral deformations proposed by \textit{T. Gao, T. Y. Li} and \textit{X. Wang} [J. Symb. Comput. 28, No. 1--2, 187--211 (1999; Zbl 0944.65055)] (which preserve the monomial structure of the system), it results that the number of variants obtained by deformation equals the expected number of solutions. For sparse systems that means algorithms of lower complexity.NEWLINENEWLINEThe main result of the paper is focused in the theorem: Let \(f_1,\dots,f_n\) be polynomials in \(\mathbb{Q}[X_1,\dots,X_n]\). There exists a probabilistic algorithm which computes a finite set of points containing the isolated common zeros of \(f_1,\dots,f_n\) in \(\mathbb{C}^n\) within a complexity which is polynomial in the size of the combinatorial structure of the system supports.NEWLINENEWLINEThe algorithm -- detailed, analyzed by its complexity and exemplified -- is called \textit{AffineSolve} and it improves the algorithm proposed by \textit{G. Jeronimo, G. Matera, P. Solernó} and \textit{A. Waissbein} [Found. Comput. Math. 9, No. 1, 1--50 (2009; Zbl 1167.14039)].NEWLINENEWLINEAlthough it is not mentioned in the paper, this result can be used in several other domains which are based on solving polynomial equation systems, like coding theory or dynamical systems.
- Affine solution sets of sparse polynomial systems
- scientific article; zbMATH DE number 1827070
- Deformation techniques for sparse systems
- Triangular sets for solving polynomial systems: a comparative implementation of four methods
- Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
- scientific article; zbMATH DE number 1263385
- scientific article; zbMATH DE number 1552220
- Systems of polynomial equations, higher-order tensor decompositions, and multidimensional harmonic retrieval: a unifying framework. Part I: the canonical polyadic decomposition
- Solving polynomial equations. Foundations, algorithms, and applications
- The complexity and geometry of numerically solving polynomial systems
- A convex geometric approach to counting the roots of a polynomial system
- A Gröbner free alternative for polynomial system solving
- A Polyhedral Method for Solving Sparse Polynomial Systems
- Algorithms in real algebraic geometry
- Bernstein's theorem in affine space
- 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 for sparse systems
- Dynamic enumeration of all mixed cells
- Efficient incremental algorithms for the sparse resultant and the mixed volume
- Finding all isolated zeros of polynomial systems in \(\mathbb{C}^n\) via stable mixed volumes
- Finding mixed cells in the mixed volume computation
- Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
- How to count efficiently all affine roots of a polynomial system
- scientific article; zbMATH DE number 3620034 (Why is no real title available?)
- scientific article; zbMATH DE number 1206418 (Why is no real title available?)
- scientific article; zbMATH DE number 575960 (Why is no real title available?)
- scientific article; zbMATH DE number 1069614 (Why is no real title available?)
- scientific article; zbMATH DE number 2051430 (Why is no real title available?)
- Mixed volume computation for semi-mixed systems
- Mixed-volume computation by dynamic lifting applied to polynomial system solving
- Modern computer algebra
- Newton polyhedra and toroidal varieties
- Newton polytopes and the Bezout theorem
- Straight-line programs in geometric elimination theory
- The BKK root count in $\mathbf {C}^n$
- The computational complexity of the Chow form
- The number of roots of a system of equations
- The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
- Deformation techniques for sparse systems
- Affine solution sets of sparse polynomial systems
- Homotopy techniques for solving sparse column support determinantal polynomial systems
- Solving decomposable sparse systems
- Computing critical points for invariant algebraic systems
- Solving determinantal systems using homotopy techniques
- Elimination for generic sparse polynomial systems
- On the multiplicity of isolated roots of sparse polynomial systems
- scientific article; zbMATH DE number 1736029 (Why is no real title available?)
- Toric eigenvalue methods for solving sparse polynomial systems
- A complexity chasm for solving sparse polynomial equations over \(p\)-adic fields. Extended abstract
- Efficiently Computing Real Roots of Sparse Polynomials
- Sparse systems and algorithmic equidimensional decomposition
- Global residues for sparse polynomial systems
This page was built for publication: Computing isolated roots of sparse polynomial systems in affine space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q410703)
