Solving polynomial systems by polyhedral homotopies
type: Item
instance of: scholarly article
title: Solving polynomial systems by polyhedral homotopies
zbMATH Open document ID: 0945.65052
published in: Taiwanese Journal of Mathematics
publication date: 2000-09-21T00:00:00Z
review text: This article gives an introduction to the method of homotopy continuation for finding isolated roots over \((\mathbb{C}^*)^n\) and recent developments in this field. This method for finding roots was developed by \textit{C. B. Garcia} and \textit{W. I. Zangwill} [Lect. Notes Econ. Math. Syst. 174, 481-497 (1980; Zbl 0428.90085)], but until recently its computational complexity had been proportional to the maximum possible number of isolated roots of a system (given by the Bézout number) rather than the actual number of isolated roots a system has. \textit{B. Huber} and \textit{B. Sturmfels} [Math. Comput. 64, No. 212, 1541-1555 (1995; Zbl 0849.65030)] developed the polyhedral homotopy, which considerably reduces the number of extraneous paths (paths that don't lead to a root) that must be followed. This article discusses some new developments of this method. Thoroughly reviewing both the author's work (with various co-authors) and Huber and Sturmfels' approach, the article gives a clear explanation of Bernshtein's theory of root counting and the polyhedral homotopy, along with a detailed account of the algorithm for finding all isolated roots by the polyhedral homotopy method. The article also explains how the ``cheater's homotopy'' can be used as an alternative to the homotopy based on stable mixed volumes that Huber and Sturmfels developed. Finally, the article mentions several areas that need further investigation.
Mathematics Subject Classification ID: 65H10
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 93B27
zbMATH DE Number: 1370633
zbMATH Keywords: polynomial systems
zbMATH Keywords: homotopy continuation
zbMATH Keywords: polyhedral homotopy
zbMATH Keywords: Bernshtein theory
zbMATH Keywords: isolated roots
zbMATH Keywords: computational complexity
zbMATH Keywords: root counting
author: Tien-Yien Li
reviewed by: Alyson Reeves
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.11650/twjm/1500407124
OpenAlex ID: W1782133069
DOI: 10.11650/TWJM/1500407124
Recommended article: Finding all isolated zeros of polynomial systems in \(\mathbb{C}^n\) via stable mixed volumes
Recommended article: The BKK root count in $\mathbf {C}^n$
Recommended article: A Polyhedral Method for Solving Sparse Polynomial Systems
Recommended article: A new start system for solving deficient polynomial systems using continuation
Recommended article: The granularity of parallel homotopy algorithms for polynomial systems of equations
Recommended article: A special homotopy continuation method for a class of polynomial systems
Recommended article: Homotopies for solving polynomial systems within a bounded domain
Recommended article: Polyhedral end games for polynomial continuation
Recommended article: Q3811597
Recommended article: The random product homotopy and deficient polynomial systems
description: scientific article; zbMATH DE number 1370633