Title: Homotopies exploiting Newton polytopes for solving sparse polynomial systems
Authors: Verschelde, Jan ×
Verlinden, Pierre
Cools, Ronald #
Issue Date: 1994
Publisher: SIAM, Philadelphia, PA
Series Title: SIAM Journal on Numerical Analysis vol:31 pages:915-930
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 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.
ISSN: 0036-1429
Publication status: published
KU Leuven publication type: IT
Appears in Collections:NUMA, Numerical Analysis and Applied Mathematics Section
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science