Title: Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
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, ...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.Read More
Publication Year: 1994
Publication Date: 1994-06-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 203
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot