Next: The Test Database of Up: PHCpack: a general-purpose solver Previous: On Portability: Computers and

# Putting it all together: one Black-Box Solver

Here the key ingredients are presented to build an overall, general-purpose solver that is reliable and efficient. This allows to solve polynomial systems simply by typing

   phc -b input output

after the prompt.

The outline of the black-box solver is as follows:


1. Homotopy Construction :
1.1. Computation of root counts :
D   : total degree;
BZ : multi-homogeneous B'ezout number,
based on a heuristically generated partition;
BS : general linear-product B'ezout number,
based on a heuristically generated set structure;
V : mixed volume, by dynamic lifting, when #different supports ,		 		 		 		 by static lifting otherwise.
1.2. Construction of start system,
corresponding to the minimal and least expensive root count.
2. Polynomial Continuation :
2.1. Coefficient and variable scaling.
2.2. Tracking of the solution paths.
2.3. Root refinement on the de-scaled solutions.


The computation of root counts by four different methods provides already important information about the problem class. Even though the mixed volume always yields the lowest bound, the construction of the corresponding start system requires continuation and is computationally much more expensive to solve than a linear-product start system. The latter start system is preferred when any of the Bézout numbers equals the mixed volume.

Practical experiments show that scaling the coefficients really helps to smoothen the continuation. For a discussion of scaling see  [Morgan, Sommese, and Watson 1989] or [Morgan 1987].


The output file contains:
1. The root counts D, BZ, BS, and V.
2. Start system with start solutions.
3. Settings of the path tracker.
4. Results of polynomial continuation on the scaled system.
5. Solutions of original system as output of the root refiner.
6. Timings for the stages and timing summary at the end.


End games are not invoked in the black-box solver, because the determination of the end game operation range tends to be problem dependent. The idea behind this black-box solver is to get quickly an idea of the complexity of the system while providing many root counts. To examine singularities and other degeneracies we recommend switching to the tool mode of PHC.

Next: The Test Database of Up: PHCpack: a general-purpose solver Previous: On Portability: Computers and
Jan Verschelde
3/7/1999