# 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.

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

- [2]
- 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.