Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems

TLDR

The BKK bound, defined as the mixed volume of the Newton polytopes, provides a sharp upper bound on the number of isolated solutions of sparse polynomial systems in (ℂ∖{0})^n. The paper seeks to find all isolated solutions of a polynomial system. An algorithm is presented to compute the BKK bound and construct cheater’s or coefficient homotopies, which are then combined with mixed homotopy methods and random product start systems based on a generalized Bézout number. Applications illustrate the effectiveness of the new approach.

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 $\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 Bernshten’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.