Software for systems of polynomial equations

Project history

The computation of all common zeros of systems of polynomial equations is an area of interest in our department since 2 decenia. It was studied because it is a necessary step in the construction of cubature formulae, i.e. multivariate integration rules. A Fortran program to compute all common zeros and all common components of two polynomials was written by Ann Haegemans, using Sylvester's determinant. This was later extended to systems with n polynomials in n variables.

In the mid-eighties, this turned out no longer capable of solving our problems and other programs using the related method of Groebner bases, had similar difficulties. As a consequence, homotopy continuation methodes were introduced in the department by Ronald Cools in 1985. With Marc Beckers, a Pascal program was developed to solve systems of polynomial equations by homotopy continuation. They witnessed and followed the growing activity in this area during the following years. When HOMPACK appeared it was noticed that the local program was performing better on the problems related to the construction of cubature formulae. Then the idea to make this a research area on its own, was born.

In 1989, for his bachelor thesis, Jan Verschelde was asked to redesign the existing program in Ada, incorporate the available experience and recent results. He continued this work as part of his PhD research. Because the target application was the construction of cubature formulae, emphasise was put on exploiting symmetry and sparsity, two key properties of systems of polynomial equations that determine cubature formulae.

Intermediate reports on the development of PHCpack are presented in the following.

J. Verschelde and R. Cools. An Ada Workbench for Homotopy Continuation for Solving Polynomial Systems. The Ada-Belgium Newsletter, 2:23-40, 1993.

J. Verschelde and R. Cools. Polynomial homotopy continuation, a portable Ada software package. The Ada-Belgium Newsletter, 4:59-83, 1996. Proceedings of the 1996 Ada-Belgium Seminar, 22 November 1996, Eurocontrol, Brussels, Belgium.

In 1995 the research on systems of polynomial equations was incorporated as part of a project on Counting and computing all isolated solutions of systems of nonlinear equations. This project received direct support from the Fund for Scientific Research -- Flanders (F.W.O.) with additional help from the Flemish Institute for the promotion of Scientific-Technological Research in Industry (I.W.T.) and the Research Council of the K.U.Leuven.