Homotopies Exploiting Newton Polytopes
for Solving Sparse Polynomial Systems

Jan Verschelde, Pierre Verlinden, and Ronald Cools

Abstract:

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 C^n_0, C_0 = C \ 0 , of a polynomial system with a sparse monomial structure. First an algorithm is described for computing the BKK bound. Following the lines of Bernshtein'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.

Keywords: polynomial systems, homotopy continuation methods, mixed volume, BKK bound.

AMS Subject Classification: 65H10.

SIAM J. Numer. Anal. 31(3):915-930, 1994.