A Polyhedral Method for Solving Sparse Polynomial Systems
Open Access
- 1 October 1995
- journal article
- Published by JSTOR in Mathematics of Computation
- Vol. 64 (212) , 1541-1555
- https://doi.org/10.2307/2153370
Abstract
A continuation method is presented for computing all isolated roots of a semimixed sparse system of polynomial equations. We introduce mixed subdivisions of Newton polytopes, and we apply them to give a new proof and algorithm for Bernstein's theorem on the expected number of roots. This results in a numerical homotopy with the optimal number of paths to be followed. In this homotopy there is one starting system for each cell of the mixed subdivision, and the roots of these starting systems are obtained by an easy combinatorial construction.Keywords
This publication has 14 references indexed in Scilit:
- Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial SystemsSIAM Journal on Numerical Analysis, 1994
- Product formulas for resultants and Chow formsMathematische Zeitschrift, 1993
- Chow polytopes and general resultantsDuke Mathematical Journal, 1992
- Fiber PolytopesAnnals of Mathematics, 1992
- Mixed volumes of polytopesArchiv der Mathematik, 1992
- Regular triangulations of convex polytopesPublished by American Mathematical Society (AMS) ,1991
- Numerical Continuation MethodsPublished by Springer Nature ,1990
- A homotopy for solving general polynomial systems that respects m-homogeneous structuresApplied Mathematics and Computation, 1987
- Valuations on convex bodiesPublished by Springer Nature ,1983
- The number of roots of a system of equationsFunctional Analysis and Its Applications, 1979