Solving Polynomial Systems by Polyhedral Homotopies

Michigan State University, East Lansing MI

Investigators

Abstract

The project is aiming at solving polynomial systems numerically by the homotopy continuation method. Over the years, practical evidences have been given that the homotopy method is efficient, reliable and much powerful in solving polynomial systems. Recently, modeling the sparse structure of a polynomial system by its Newton polytopes leads to a major computational breakthrough called the polyhedral homotopy method. Based on it, a source code HOM4PS, produced by the PI and his students, leads all the other existing codes for solving polynomial systems in efficiency and storage requirement by a great margin. Nonetheless, there are numerous models of large polynomial systems in application still do not have a satisfactory line of attack. And it has become apparent that the numerical techniques for following homotopy paths are far from thoroughly developed for large systems. The essence of the project is the advance development in all aspects of the solver HOM4PS based on the conduct of further research to greatly enlarge the scope of its applications, especially applications to large systems. The problem of solving polynomial systems arises very frequently in various fields of science and engineering, such as formula construction, geometric intersection, inverse kinematics, robotics, power flow problems with PQ-specified bases, vision and the computation of equilibrium states of chemical reaction equations, etc. This topic has been an important research subjectin Europe. In the last decade, a considerable research effort involving seven countries and twenty universities had been directed to this problem in two consecutive major projects, PoSSo and FRISCO, supported by European Commission. As mentioned above, the code HOM4PS developed by the PI for this problem is far more advanced and the ultimate goal of the current project is a more complete high-quality block-box software which will incorporate the best state of the art to provide the general scientific community a reliable source for solving polynomial systems on a wide variety of advanced architectures.