The Internal Design: the Libraries of PHCpack

There are four large components of the software system: the mathematical library, the homotopy continuation routines, the root-counting methods, and the interface packages.

The sources of PHCpack are organized in the following tree of libraries:

 Ada                       : Ada sources of PHC
  |-- System               : 0. UNIX dependencies, e.g.: timing
  |-- Math_Lib             : 1. general mathematical library
  |      |-- Numbers       : 1.1. number representations
  |      |-- Matrices      : 1.2. matrices and linear-system solvers
  |      |-- Polynomials   : 1.3. multivariate polynomial systems
  |      |-- Supports      : 1.4. support sets and linear programming
  |-- Homotopy             : 2. homotopy and solution lists
  |-- Continuation         : 3. path-tracking routines
  |-- Root_Counts          : 4. root counts and homotopy construction
  |      |-- Product       : 4.1. linear-product start systems
  |      |-- Implift       : 4.2. implicit lifting
  |      |-- Stalift       : 4.3. static lifting
  |      |-- Dynlift       : 4.4. dynamic lifting
  |      |-- Symmetry      : 4.5. exploitation of symmetry relations
  |-- Schubert             : 5. numerical Schubert calculus
  |-- Main                 : 6. main dispatcher

The structure reflects the discrete and continuous nature of the program.

The concept of information hiding has been applied more deeply than just separating the four stages of the solver. Next are some examples on how PHC deals with polynomials.

1.

The continuation is not only separated from the choice of the homotopy, but also from the way polynomials are evaluated. This is done by providing the evaluation and differentiation of the homotopy as parameters of the path trackers.

2.

For the evaluation of polynomials, a multivariate Horner scheme is implemented at the level of the polynomial package. The precise definition is hidden to the client procedures that create and evaluate these polynomials.

3.

A polynomial homotopy can be evaluated more efficiently when the coefficients are parameters to the evaluation routines. The combination with multivariate Horner yields a powerful and flexible coefficient homotopy.

Without using this third data structure, the construction of a random coefficient start system for the cyclic 7-roots problem (924 paths to follow, about 100 cells) by means of polyhedral homotopy continuation took 4h 38m 55s 354ms cpu time. The current version takes only about 15m 49s 391ms cpu time! Polyhedral homotopies are nonlinear in the continuation parameter t and treating $t^\omega$ as just one monomial or as a polynomial of degree $\omega$ makes the difference in evaluation. This third data structure was created to deal with floating-point lifting values $\omega$ implementing a suggestion of T.Y. Li.

Note that coefficient-parameter polynomial continuation [Morgan and Sommese 1989] or cheater's homotopy  [Li, Sauer and Yorke 1989], [Li and Wang 1992] is very useful and n atural concept.

The computational bottleneck in polynomial continuation is the evaluation of polynomials. The efficiency could improve a lot if the polynomials would be known at compile time, so that optimized in-line evaluators can be used. However, to keep the program user-friendly, compilation of the program must not be required each time a new system has to be solved.