Symbolic Computation Group

In the last two decades, the homotopy continuation method has been established in the U.S. for finding the full set of isolated solutions to a polynomial system numerically. The method involves first solving a trivial system, and then deforming these solutions along smooth paths to the solutions of the target system. Recently, modeling the sparse structure of a polynomial system by its Newton polytopes leads to a major computational breakthrough in solving polynomial systems by the homotopy continuation methods. Based on an elegant formula for computing the mixed volume, the new polyhedral homotopy can find all isolated zeros of a polynomial system by following much fewer solution paths. The method has been successfully implemented and proved to be very powerful in many occasions, especially when the systems are sparse. In this talk we will elaborate the polyhedral homotopy continuation method and its resulting code HOM4PS-2.0 which leads the existing codes PHC and PHoM for the same purpose by a big margin in speed.

The homotopy continuation approach is parallel in nature, in the sense that each isolated zero is computed independently from the others. This feature makes it well-suited for advanced computer architectures. We will also present the numerical results of the parallel version of HOM4PS-2.0.