HOMOTOPIES EXPLOITING NEWTON POLYTOPES FOR SOLVING SPARSE POLYNOMIAL SYSTEMS

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 system, is a sharp upper bound for the number of isolated solutions in C0n, C0 = 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 Bezout number. Applications illustrate the effectiveness of the new approach.