Polynomial Continuation and End Games

Solution paths of polynomial homotopies do not turn back as the continuation parameter t increases, due to the regularity of the paths, as discussed in [Li and Sauer 1987]. Therefore an increment-and fix predictor-corrector method is appropriate: after each increase of t, t remains fixed while correcting the solution $\bf x$ by Newton's method. Figure 3 sketches two possible predictor schemes in the path tracker.

  

Figure 3: The secant and tangent predictor with $\lambda$ as step length.

The clustering of solution paths is avoided by tightening the tolerances of the corrector to enforce quadratic convergence of Newton's method in every step.

Only as $t \rightarrow 1$, we may have to deal with paths converging to singular solutions and with paths diverging to infinity. To this end, several end games were proposed by Morgan, Sommese and Wampler  [1991 ,1992a, 1992b] and by Sosonkina, Watson and Stewart in [1996] . Polyhedral end games  [Huber and Verschelde 1998] provide a certificate of divergence that allows to separate diverging paths from the rest, without first having to compute the actual values of the diverging paths accurately. Next we summerize the idea of [Huber and Verschelde 1998].

A solution path is represented by the following power series expansion:

$$\left\{ \begin{array} {rcl} x_i(s) & = & a_i s^{\omega_i} ... ...end{array} \right. \quad \quad t \approx 1, \quad s \approx 0.$$ (7)

The winding number m is lower than or equal to the multiplicity of the solution. We see that for a solution diverging to infinity or to a zero-component solution: $\omega_i \not= 0$.According to David Bernshtein's second theorem  [1975], this solution corresponds to a solution of the face system defined by the direction $\omega$. This face certifies the divergence.

To check whether a solution path really diverges is equivalent to the test on the value for $\omega_i$. A first-order approximation of $\omega_i$ can be computed by

$$\frac{\log\vert x_i(s_1)\vert - \log\vert x_i(s_0)\vert}{\log(s_1) - \log(s_0)} = \omega_i + O(s_0),$$ (8)

with 0 < s₁ < s₀. The above formula assumes the correct value of the winding number m. To compute m, solution paths are sampled geometrically with ratio h as s_k = h^k/m s₀. The errors on the estimates for $\omega_i$ are

An estimate for m is derived from two consecutive errors e_i^(k). Extrapolation improves this estimate.

A parallel development to make resultants deal with situations when the mixed volume overshoots the number of roots is described in [Rojas 1997].