Dense Polynomials modeled by Highest Degrees

A polynomial in one variable has as many complex solutions as its degree. A linear system has either infinitely many solutions or exactly one isolated solution in projective space. By this analogy [53] we see that Bézout's theorem generalizes these last two statements: a polynomial system has either infinitely many solutions or exactly as many isolated solutions in complex projective space as the total degree.

As the above presentation of Bézout's theorem suggests, the simplest cases are univariate and linear systems, which are used as start systems. For the example system (2), a start system  $P^{(0)}({\bf x}) = {\bf0}$ based on the total degree D is given by two univariate quartic equations x₁⁴ - c₁ = 0 = x₂⁴ - c₂, where c₁ and c₂ are randomly chosen complex numbers. Note that the computation of $D = 4 \times 4$ models the structure of the solutions of P⁽⁰⁾ as four solutions for x₁ crossed with four solutions for x₂.

The earliest approaches of this homotopy appear in [14], [19], [31], [32], and were further developed in [52], [70], [129]. The book [71] contains a very good introduction to the practice of solving polynomial system by homotopy continuation. Regularity results can be found in [54] and [131]. While this homotopy algorithm has a sound theoretical basis, the total degree is a too crude upper bound for the number of affine roots to be useful in most applications.

Multi-homogeneous homotopies were introduced in [72,73] and applied to various problems in mechanism design, see e.g. [118,119]. Similar are the random product homotopies [55,56], applying intersection theory in [58], but less suitable for automatic procedures. For our running example (2), we follow the approach of multi-homogenization and we group the unknowns according to the partition $Z = \{ \{ x_1 \} , \{ x_2 \} \}$. The corresponding degree matrix M_Zhas in its (i,j)-th entry the degree of the i-th polynomial in the variables of the j-th set of Z. The 2-homogeneous Bézout bound B_Z is the permanent of M_Z.

$$\begin{array}{l} P(x_1,x_2) = \\ ~~~~~ \left\{ \begin{arr... ... 4 \times 2 + 3 \times 1 \\ & \! \! = \! \! & 11 \end{array}$$ (10)

The computation of the permanent follows the expansion for the determinant, except for the permanence of signs, as it corresponds to adding up the roots when solving the corresponding linear-product start system:

$$P^{(0)}({\bf x}) = \left\{ \begin{array}{c} {\displaystyle... ...\prod_{i=1}^2 (x_2 - \beta_{2i})} = 0 \\ \end{array} \right.$$ (11)

In most applications the grouping of variables follows from their meaning, e.g.: for eigenvalue problems  $A {\bf x} = \lambda {\bf x}$, $Z = \{ \{ \lambda \} , \{ x_1, x_2 ,\ldots ,x_n \} \}$. Efficient permanent evaluations in conjunction with exhaustive searching algorithms for finding an optimal grouping were developed in [120]. In case the number of independent roots equals the Bézout bound, interpolation methods [105] are useful.

Partitioned linear-product start systems were developed in [109] elaborating the idea that several different partitions can be used for the polynomials in the system. Motivated by symmetric applications [107], general linear-product start system were proposed in [106]. These start systems are based on a supporting set structure S which provides a more refined model of the degree structure of a polynomial system.

$$S = \begin{array}{\vert c\vert} \hline \{ x_1 \} \{ x_1 , ... ...1 \} \{ x_1 , x_2 \} \{ x_1 \} \{ x_2 \} \\ \hline \end{array}$$ (12)

To compute the bound formally, one collects all admissible n-tuples of sets, picking one set out of every row in the set structure.

$$\begin{array}{rl} B_S = & \! \! \! \! \char93 \{ ( \{ x_1 \... ...x_1 \} , \{ x_2 \} ) ( \{ x_1 \} , \{ x_2 \} ) \} \end{array}$$ (13)

Each admissible pair corresponds to a linear system that leads to a solution of a generic start system:

$$P^{(0)}({\bf x}) = \left\{ \begin{array}{c} (x_1+c_{11})(x... ...+c_{23})(x_1+c_{24})(x_2+c_{25}) = 0 \\ \end{array} \right.$$ (14)

This start system has B_S = 10 solutions. In [106], the following theorems were proven.

Theorem 5.1   Except for a choice of coefficients belonging to an algebraic set, there are exactly B_S regular solutions to a random linear-product system based on the set structure S.

The proof of the theorem consists in collecting the determinants that express the degeneracy conditions. These determinants are polynomials in the coefficients and vanish at an algebraic set.

Theorem 5.2   All isolated solutions to  $P({\bf x}) = {\bf0}$ lie at the end of some solution path defined by a convex-linear homotopy originating at a solution of a random linear-product start system, based on a supporting set structure for P.

The idea of the proof is to embed the homotopy into an appropriate projective space and to consider the projection of the discriminant variety as an algebraic set for the continuation parameter. See [63] for an alternative proof.

A general approach to exploit product structures was developed in [80]. For systems whose polynomials are sums of products one may arrive at a much tighter bound replacing the products by one simple product. An efficient homotopy to solve the nine-point problem in mechanical design was obtained in this way.

The complexity of this homotopy based on the total degree is addressed in [10] where $\alpha$-theory is applied to give bounds on the number of steps that is needed to trace the solution paths. A major result is that one can decide in polynomial time whether an average polynomial system has a solution. A similar analysis of Newton's method in multi-projective space was recently done in [17].

While the above complexity results apply to random systems, the problem of automatically extracting and exploiting the degree structure of a polynomial system is a much harder problem. Finding an optimal multi-homogeneous grouping essentially requires the enumeration of all partitions [120]. With supporting set structures one may obtain a high success rate, see [63] for a efficient heuristic algorithm. Recent software extensions for finding optimal partitioned linear-product start systems are in [128].