The design: PHC as workbench

Our software forms the basis to perform computational explorations with the intention to gain more insight into the complexity of the problem. Therefore, instead of aiming at a black-box solver, which works well on average polynomial systems (which are not practical applications of course), a more open design, i.e., towards the development of a workbench, turns out to be more interesting.

We distinguish four large components of our software:

1. The mathematical library contains the prerequisites needed, not typically related to polynomial homotopy continuation.
2. Root counting methods based on Bézout's and Bernshtein's theorem have been implemented, as well as the corresponding homotopy constructors.
3. Path following consists of the predictor-corrector methods and the corresponding data abstractions for tuning parameters.
4. The interface represents all communication with the user, who can be either the end-user or the application programmer.

The concept of information hiding has been applied more deeply than just separating the four stages of the solver. We give 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 achieved by providing the evaluation and differentiation of the homotopy as generic parameters of the path trackers.

2. For the evaluation of polynomials, a multivariate Horner scheme has been provided, at the level of the polynomial package. The precise definition is hidden to the client packages that create and evaluate these polynomials.

3. A polynomial homotopy can be evaluated just as any other polynomial system. More flexibility is provided when the coefficients are parameters to the evaluation routines. The combination with multivariate Horner yields both a powerful and flexible coefficient homotopy.

Dynamic memory allocation should not prevent efficient number crunching by interference of garbage collection. Therefore all needed data structures are allocated before the continuation starts and are only freed after the numerical work is accomplished. The same strategy is followed in the root counting methods.

Only a careful design that matches the actual needs of a solver can keep a package of more than 50,000 lines maintainable.