Finding All Isolated Zeros of Polynomial Systems inCnvia Stable Mixed Volumes

To find all the isolated zeroes of a polynomial system P(x) inCn (as opposed to in (C * )n) via the polyhedral homotopy of Huber and Sturmfels (1997), one first finds all stable mixed cells in a special polyhedral subdivision called a stable mixed subdivision and creates a fine mixed subdivision for each stable mixed cell. The stable mixed subdivision depends solely on the monomial structure of P and a convex geometric lifting process. One then solves a collection of subsystems corresponding to the stable mixed cells, and uses these solutions as starting points for a finite set of nonlinear homotopies. This final set of homotopies give a dramatic computational improvement over earlier homotopy algorithms, but the initial steps of finding the stable mixed cells and their fine mixed subdivisions require many costly recursiveliftings. The purpose of this paper is to present a new strategy using a single lifting which quickly (and simultaneously) builds the stable mixed subdivision, the fine mixed subdivisions of the stable mixed cells, and the necessary subsystems.