Finding all isolated zeros of polynomial systems in \(\mathbb{C}^n\) via stable mixed volumes
type: Item
instance of: scholarly article
title: Finding all isolated zeros of polynomial systems in \(\mathbb{C}^n\) via stable mixed volumes
zbMATH Open document ID: 0944.65055
published in: Journal of Symbolic Computation
publication date: 2000-09-13T00:00:00Z
review text: In 1997, \textit{B. Huber} and \textit{B. Sturmfels} [Discrete Comput Geom. 17, No. 2, 137-141 (1997; Zbl 0891.65055)] developed a method, based on the polyhedral homotopy, for finding all of the isolated roots in \(\mathbb{C}^n\) of a polynomial system. The method requires one to find all stable mixed cells in the stable mixed subdivision of a polyhedron, and then to create a fine mixed subdivision for each such cell. While this greatly reduces the number of extraneous (not leading to a root) paths that must be followed in the ensuing homotopy continuation, the steps described above may require several recursive liftings. This paper presents an algorithm which simultaneously builds the stable mixed subdivision and the fine mixed subdivisions of the stable mixed cells using a single lifting. The algorithm has been implemented, and results (without timings) are presented for 7 well-known examples.
Mathematics Subject Classification ID: 65H10
Mathematics Subject Classification ID: 32A60
Mathematics Subject Classification ID: 65H20
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 30C15
zbMATH DE Number: 1369544
zbMATH Keywords: polynomial systems
zbMATH Keywords: homotopy continuation
zbMATH Keywords: polyhedral homotopy
zbMATH Keywords: stable mixed volumes
zbMATH Keywords: isolated roots
zbMATH Keywords: mixed subdivision
zbMATH Keywords: algorithm
author: Tangan Gao
author: Tien-Yien Li
author: Xiaoshen Wang
reviewed by: Alyson Reeves
MaRDI profile type: Publication
full work available at URL: jsco.1998.0272
OpenAlex ID: W2051751555
cites work: The number of roots of a system of equations
cites work: A Polyhedral Method for Solving Sparse Polynomial Systems
cites work: Bernstein's theorem in affine space
cites work: Newton polyhedra and the genus of complete intersections
cites work: Newton polytopes and the Bezout theorem
cites work: Q4356576
cites work: The Cheater’s Homotopy: An Efficient Procedure for Solving Systems of Polynomial Equations
cites work: The BKK root count in $\mathbf {C}^n$
cites work: A convex geometric approach to counting the roots of a polynomial system
cites work: Counting affine roots of polynomial systems via pointed Newton polytopes
cites work: Mixed-volume computation by dynamic lifting applied to polynomial system solving
DOI: 10.1006/JSCO.1998.0272
description: scientific article; zbMATH DE number 1369544