Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
Jan Verschelde, Pierre Jacques Verlinden, Ronald Cools · SIAM Journal on Numerical Analysis · 1994
This paper is concerned with the problem of finding all isolated solutions of a polynomial system. The BKK bound, defined as the mixed volume of the Newton polytopes of the polynomials in the system, is a sharp upper bound for the number of isolated solutions in $\mathbb{C}_0^n ,\mathbb{C}_0 = \mathbb{C} \backslash \{ 0\} $, of a polynomial system with a sparse monomial structure. First an algorithm is described for computing the BKK bound. Following the lines of Bernshte[Formula: see text]n’s proof, the algorithmic construction of the cheater’s homotopy or the coefficient homotopy is obtained. The mixed homotopy methods can be combined with the random product start systems based on a generalized Bézout number. Applications illustrate the effectiveness of the new approach.