Solving polynomial systems by polyhedral homotopies

Michigan State University, East Lansing MI

Investigators

Abstract

In the last two decades, the homotopy continuation method for solving polynomial systems has been established and proved to be reliable and efficient. Resulting from a previous project, supported by NSF Grant DMS-9804846, a source code, HOM4PS, was produced. Excellent performance of this code on a large collection of polynomial systems in a wide variety of applications provides practical evidence that the newly developed methods constitute a powerful general purpose solver. Nontheless, there are still numerous models of polynomial systems in applications which do not have a satisfactory line of attack. Those models provide a rich source of interesting and challenging problems with strong mathematical content. The essence of the proposed project is the advance development of the solver based on the conduct of further research to greatly enlarge the scope of its applications. The ultimate goal is a more complete high-quality block-box solfware which will incorporate the best state of the art to provide the general scientific community a reliable source for solving polynomial systems in practice. The problem of solving polynomial systems has been, and will continue to be, one of the most important subjects in both pure and applied mathematics. The need to solve systems of polynomial equations arises very frequently in various fields of science and engineering, such as, formula construction, geometric intersection, inverse kinematics, robotics, vision and the computation of equilibrium states of chemical reaction equations, etc. In recent years (1993-1999), a considerable research effort in Europe had been directed to this problem in two consecutive major projects, PoSSo (Polynomial System Solving) and FRISCO (FRamework for Integrated Symbolic/numerical COmputation), supported by European Commission with thirteen university teams in seven European countries involved. Those research projects focused on the development of the already well-established Groebner basis methods within the framework of computer algebra. Their reliance on symbolic manipulation makes those methods seem somewhat limited to relatively small problems. In contrast, the approch by the homotopy continuation method in this project is numerical and exhibits much powerful application results.