HOMOTOPIES EXPLOITING NEWTON POLYTOPES FOR SOLVING SPARSE POLYNOMIAL SYSTEMS

This paper is concerned with the problem of finding all isolated solut ions of a polynomial system. The BKK bound, defined as the mixed volum e of the Newton polytopes of the polynomials in system, is a sharp upp er bound for the number of isolated solutions in C0n, C0 = C\{0}, of a polynomial system with a sparse monomial structure. First an algorith m is described for computing the BKK bound. Following the lines of Ber nshtein's proof, the algorithmic construction of the cheater's homotop y or the coefficient homotopy is obtained. The mixed homotopy methods can be combined with the random product start systems based on a gener alized Bezout number. Applications illustrate the effectiveness of the new approach.