Numerical Software for Solving Polynomial Systems

In computer algebra one wants to compute exactly as long as possible and to defer the approximate calculations to the very last end. Exactly the opposite way is taken in homotopy methods: here we use floating-point arithmetic and only increase the precision when needed.

Next we mention programs with special features for polynomial systems. See [5, Chapter VIII] for a list of available software for path following. HOMPACK [74,124] is a general continuation package with a polynomial driver. It has been parallelized [6,36], extended with an end game [95], and upgraded [126] to Fortran 90. POLSYS_PLP [128] provides linear-product root counts to be used in conjunction with HOMPACK90. The Fortran code for CONSOL is contained in [71, Appendix 6]. The C-program pss [66] applies homotopy continuation with verification by $\alpha$ -theory. Pelican [39,41] implements in C the polyhedral methods of [40]. Efficient Fortran software for polyhedral continuation with facilities to compute all affine roots is used in [29]. The computation of mixed volumes with the C program mvlp [23,24] is a crucial step for sparse resultants [117]. A distributed version has been created in [34].

PHC is written in Ada and originated during the doctoral research of the author [113]. Executable versions were first released at the PoSSo open workshop on software [111]. The public release of the sources is described in [115]. The package is organized as a tool box, organized along four stages of the solver. Figure 13 presents the flow of the solver. The package is menu-driven and file-oriented. A general-purpose black-box solver is available.

**Figure 13:** The four stages in the flow of the PHC solver.
$\begin{figure} \begin{center} \begin{picture} (360,145)(10,0) \par\put(20,120){\... ...ine(1,2){5}} \put(226,102){\line(-1,2){5}} \end{picture}\end{center}\end{figure}$

The new second release of PHC uses Ada 95 concepts in the construction of the mathematical library. It is developed with the freely available gnu-ada compiler (currently at version 3.11p) on various platforms. To run the software no compilation is needed, as binaries are available for Unix Workstations: running SUN Solaris and SGI Irix, and Pentium PCs: running Linux and Solaris. The portability of PHC is ensured by the gnu-ada compiler.

Another main feature of the second release are the homotopy methods for the Schubert calculus. Implementing those homotopies was a matter of plugging in the equations and calling the path trackers. The third release of the package should offer a more comprehensive environment to construct homotopies, providing an easier access to the two main computational engines: mixed-volume computation and polynomial continuation.