Introduction

The presented software package PHC implements homotopy continuation methods to compute numerically approximations to all isolated solutions of a system of n polynomial equations in n unknowns.

The name Polynomial Homotopy Continuation unites the three key concepts of the method. Since we solve polynomial systems we exploit the algebraic structure to count the roots and to construct a start system. By continuation methods the known solutions of the start system are extended to the desired solutions of the target system. This deformation is defined by the homotopy, that is a family of systems connecting start and target system.

The following intuitive reasoning might shed a light on the hardness of the problem. Not surprisingly, evaluating a multivariate polynomial can be done in polynomial time, i.e., in time proportional to a polynomial function in the dimension, degrees and number of terms. Computing one solution is NP-hard, because we may apply the following non-deterministic algorithm: guess a root by some oracle and verify whether it satisfies the equations. This verification runs in polynomial time. Computing all solutions is harder, because there exists no polynomial-time algorithm to verify whether a guessed number of solutions gives the right number of solutions. This counting problem is said to be #P-hard. Hence our problem is intractable [Garey and Johnson 1979] for growing dimension and increasing degrees. Consequently, the computations are restricted to a fixed dimension n and the complexity is measured in terms of the output size, that is the number of solutions. See [Blum, Cucker, Shub, and Smale 1997] for the complexity of Bézout's theorem.

The central concept in polynomial homotopy continuation is the root count, because it determines the number of solution paths that need to be traced. Recent research has strived to develop sharp root counts that lead to homotopies with an optimal number of paths. The root count is also a vital instrument in validating numerical results. This term encompasses Bézout numbers, mixed volumes, and combinatorial counts from the Schubert calculus in enumerative geometry.

The history of homotopy continuation for polynomial systems can be roughly divided into two eras, each spanning about one decade. The first decade was focussed on applying Bézout's theorem for counting the solutions. Milestone publications are the introductory paper [Li 1987], the book [Morgan 1987], and the survey [Watson 1986]. Publicly available software packages are CONSOL [Morgan 1987] and HOMPACK  [Watson, Billups, and Morgan 1987], recently upgraded to Fortran 90 [Watson, Sosonkina, Melville, Morgan, and Walker 1997]. During the last ten years, root-counting methods have been developed to exploit the structure of a polynomial system. The novel methods are of a symbolic-numeric nature [Emiris 1998]. Progress in homotopy continuation for polynomial systems [Li 1997] benefited from the interaction between combinatorics, algebraic geometry and applied mathematics [Sturmfels 1998]. The polyhedral methods have brought homotopy continuation into the literature on computational algebraic geometry  [Cox, Little, and O'Shea 1998]. New publicly available software packages are Pelican [Huber 1995] and PHC. Recently, optimal homotopies were presented for computing linear subspace intersections in enumerative geometry, see [Sottile 1997], [Huber, Sottile, and Sturmfels 1998] and [Verschelde 1998].

The aim of this paper is to give an overview on how the algorithms in PHC are used in practice to solve polynomial systems. In the next section related software packages are mentioned. PHC offers a great variety of root-counting methods, as explained in section three. The fourth section contains some basics about polynomial continuation. Sections five, six and seven describe the general flow, the operation modes of the main program, and the internal structure of the package. The software is portable, computer-compiler experiences are given in section eight. In sections nine and ten the outline of the black-box solver is presented, along with its practical performance on a large collection of applications. Before the conclusions, information on how to obtain and install the software is listed.