Solving polynomial systems by polyhedral homotopies
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.
scientific article; zbMATH DE number 1370633