Solving polynomial systems by polyhedral homotopies (Q1809738)

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.