Abstract:

The polyhedral homotopy (B.Huber and B.Sturmfels (1995)) has been established as a powerful numerical method for computing all isolated solutions of a polynomial system of equations in complex variables. Finding all mixed cells of the support of a polynomial system plays an essential role in this method. Using the mixed cells, we construct a family of polyhedral homotopy functions between start systems, whose zeros can be computed easily, and the original polynomial system. Starting from all solutions of every start system, we then trace all solution curves, which reach isolated solutions of the original system, of every polyhedral homotopy functions.

In this talk, we first survey the polyhedral homotopy method, and next present an efficient enumeration algorithm for all mixed cells. Finding all mixed cells is formulated via an linear programming problem as a vertex enumeration problem of a polyhedral set with an additional combinatorial condition. It is essential in computational efficiency how we construct an enumeration tree among a family of linear inequalities induced from the enumeration problem. Our method constructs an enumeration tree dynamically so that we can prune a lot of worthless subtrees which do not contain any mixed cells. We show by numerical results that our dynamic method works very more efficiently on larger scale polynomial systems than existing methods.

Joint work with Masakazu Kojima and Akiko Takeda.