A group led by the PI has successfully developed a software package, HOM4PS-2.0, implementing the "polyhedral homotopy continuation" method for solving polynomial systems. The solver leads existing software packages for solving polynomial systems in speed by a large margin. The essence of the proposed project is the further development in all aspects of the solver HOM4PS-2.0. In particular, for the need of solving larger polynomial systems, a major aspect of the project is the advanced development of the parallel version of the solver. The landscape of computation hardware is quite different from even a decade ago. Developments in new processor design and network technology have allowed supercomputers and computer clusters to grow larger and faster than ever, including new ideas such as cycle scavenging, grid computing, virtual supercomputers, multiple cores, and GPUs (graphics processing units). The proposed project will investigate and implement versions of HOM4PS-2.0 that take optimum advantage of heterogeneous computing platforms, with special emphasis on clusters, cloud computing, multicore and GPUs. In addition we plan to find ways to implement highly serial parts of the original algorithm, such as mixed volume computation and path-jumping detection on parallel architectures. The proposed project intends to fully incorporate all the cutting-edge parallel computing technologies in our solver for solving larger and larger polynomial 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, computer vision and the computation of equilibrium states of chemical reaction equations, etc. Science and engineering problems pose an increasing demand for solving larger and larger polynomial systems. To deal with such large systems, more computing resources are needed to greatly enlarge the capability of our solver, HOM4PS-2.0. For this purpose the parallelization of the original algorithms becomes inevitably essential. Computational technology is experiencing a major sea change in which one either rides the wave or goes under. To embrace this challenge, the core of the project is to fully incorporate the cutting-edge parallel computing technologies for solving larger and larger polynomial systems. The ultimate goal is a more powerful suite of high-quality software package which will provide the scientific community a reliable source for solving polynomial systems in practice.

National Science Foundation (NSF)
Division of Mathematical Sciences (DMS)
Standard Grant (Standard)
Application #
Program Officer
Junping Wang
Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
Michigan State University
East Lansing
United States
Zip Code