Sparse Polynomial Systems solved by Polyhedral Homotopies

The simplest system in the polytope model that still has isolated solutions in  $({\Bbb C}^*)^n$ has exactly two terms in every equation. Polyhedral homotopies [40] solve systems with random complex coefficients starting from sparser subsystems. For (2), the homotopy with supports  $\widehat {\cal A}$ as in (16) is

$${\widehat P}(x_1,x_2,t) = \left\{ \begin{array}{r} c_1 x... ...end{array} \right. \quad {\rm with~} c_i,c'_i \in {\Bbb C}^*.$$ (21)

The exponents of t are the values of the lifting $\omega$applied to the supports.

To find the start systems, we look at Figure 8, at the subdivision that is induced by this lifting process. The start systems have Newton polytopes spanned by one edge of the first and one edge of the second polytope. Since the two cells that contribute to the mixed volume are characterized by their inner normals $\alpha$ and $\beta$satisfying (17) we denote the start systems respectively by $P^\alpha$ and $P^\beta$. To compute start solutions, unimodular transformations make the system triangular as follows. After dividing the equations so that the constant term is present, we apply the substitution x₁ = y₂, x₂ = y₁^-1 y₂³ on $P^\alpha$ as follows:

$$P^{\alpha}({\bf x}) = \left\{ \begin{array}{r} x_1^3 x_2... ...c''_1 = 0 \\ y_1^{-2} y_2^7 + c''_2 = 0 \end{array} \right.$$ (22)

The substitution in (22) is apparent in the notation (as used in [64]) ${\bf x}^V = ({\bf y}^U)^V = {\bf y}^{VU} = {\bf y}^L$ elaborated as

$$\begin{array}{rcl} \left( \begin{array}{c} x_1^3 \cdot x_2... ..._2^0 \\ y_1^{-2} \cdot y_2^7 \end{array} \right). \end{array}$$ (23)

The exponents are calculated by the factorization VU = L:

$$\left[ \begin{array}{rr} 3 & -1 \\ 1 & 2 \end{array} \right... ...eft[ \begin{array}{rr} 1 & 0 \\ -2 & 7 \end{array} \right] .$$ (24)

Since $\det(U) = 1$, the matrix U is called unimodular.

The polyhedral homotopy (21) directly extends the solutions of $P^\alpha$ to the target system. To obtain a homotopy starting at the solutions of $P^\beta$, we substitute in (21) $x_1 \leftarrow {\widetilde x}_1 t^{\beta_1}$, $x_2 \leftarrow {\widetilde x}_2 t^{\beta_2}$and clear out the lowest powers of t. This construction appeared in [40] and provides an algorithmic proof of the following theorem.

Theorem 5.3 (Bernshtein [7, Theorem A])   For a general choice of coefficients for P, the system $P({\bf x}) = {\bf0}$ has exactly as many regular solutions as its mixed volume  $V_n({\cal Q})$.

The original algorithm Bernshtein used in his proof was implemented in [110].

For the numerical stability of polyhedral continuation, it is important to have subdivisions induced by low lifting values, since those influence the power of the continuation parameter. In [112] explicit lower bounds on integer lifting values were derived, but unfortunately the dynamic lifting algorithm does not generalize that well [65] if one is only interested in the mixed cells of a mixed subdivision. A balancing method was proposed in [30] to improve the stability of homotopies induced by random floating-point lifting values.

Once all solutions to a polynomial system with randomly generated coefficients are computed, we use cheater's homotopy to solve any specific system with the same Newton polytopes. One could say that polyhedral homotopies have removed the cheating part. The main advantage of polyhedral methods is that the mixed volume is a much sharper root count in most applications, leading to fewer paths to trace. They also allow more flexibility to exploit symmetry as demonstrated in [108].

In case the system has fewer isolated solutions than the mixed volume, we consider the face systems. Define the face of a polynomial p with support A as follows:

$$p({\bf x}) = \sum_{{\bf a} \in A} c_{\bf a} {\bf x}^{\bf a} ... ...bf a} {\bf x}^{\bf a} \quad \mbox{for } {\bf v} \not= {\bf0}.$$ (25)

For ${\bf v} \not= {\bf0}$, the corresponding face system of P is $\partial_{\bf v} P = ( \partial_{\bf v} p_1, \partial_{\bf v} p_2, \ldots , \partial_{\bf v} p_n )$.

Theorem 5.4 (Bernshtein [7, Theorem B])   Suppose $V_n({\cal Q}) > 0$. Then, $P({\bf x}) = {\bf0}$ has fewer than  $V_n({\cal Q})$isolated solutions if and only if $\partial_{\bf v} P({\bf x}) = {\bf0}$has a solution in $({\Bbb C}^*)^n$, for  ${\bf v} \not= {\bf0}$.

As is the case for our running example (2), the Newton polytopes may be in generic position such that for any nonzero choice of the coefficients, the system has exactly as many isolated solutions as the mixed volume. In practical applications however, how can we decide whether paths are really going towards infinity? Relying on the actual computed values is arbitrarily, because 10⁴ is as far from infinity as 10⁸, so we need algebraic structural data to certify the divergence.

In the polyhedral end game [43] solution paths are represented by power series expansions:

$$\left\{ \begin{array}{rcl} x_i(s) & = & a_i s^{v_i} ( 1 +... ...nd{array} \right. \quad \quad t \approx 1, \quad s \approx 0.$$ (26)

The winding number m is lower than or equal to the multiplicity of the solution. For a solution diverging to infinity or to a zero-component solution we observe that $v_i \not= 0$. According to Theorem 5.4, this solution vanishes at a face system $\partial_{\bf v} P$(same $\bf v$ with components v_i as in (26)), certifying the divergence.

To check whether a solution path really diverges is equivalent to the test on the value for v_i. A first-order approximation of v_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)} = v_i + O(s_0),$$ (27)

with 0 < s₁ < s₀. The above formula assumes the correct value for 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 v_i are

$$(\log\vert x_i(s_k)\vert - \log\vert x_i(s_{k+1})\vert) - (\log\vert x_i(s_{k+1})\vert - \log\vert x_i(s_{k+2})\vert)$$ e_i^(k) = (28)

= c₁ h^k/m s₀ (1 + O(h^k/m)). (29)

An estimate for m is derived from two consecutive errors e_i^(k). Extrapolation improves this estimate. So, by an inexpensive side calculation at the end of the paths, we obtain important structural algebraic information about the system.

Recall that $V_n({\cal Q})$ count the roots in  $({\Bbb C}^*)^n$. Using Newton polytopes to count affine roots (i.e.: in  ${\Bbb C}^n$ instead of  $({\Bbb C}^*)^n$) was proposed in [85] with the notion of shadowed polytopes obtained by the substitution $x_i \leftarrow x_i + c_i$ for arbitrary constants c_i. To arrive at sharper bounds, it suffices (see [62] and [86]) to add a random constant to every equation. Stable mixed volumes [42] provide a generically sharp affine root count. The constructions in [26] and [29] avoid the use of recursive liftings to compute stable mixed volumes. Further developments and generalizations can be found in [87].