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
based on the
total degree *D* is given by two univariate quartic equations
*x*_{1}^{4} - *c*_{1} = 0 = *x*_{2}^{4} - *c*_{2},
where *c*_{1} and *c*_{2} are randomly chosen complex numbers.
Note that the computation of
models the structure of the
solutions of *P*^{(0)} as four solutions for *x*_{1} crossed with four solutions
for *x*_{2}.

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
.
The corresponding degree matrix *M*_{Z}has 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}.

(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:

(11) |

In most applications the grouping of variables follows from their meaning, e.g.: for eigenvalue problems , . 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.

(12) |

To compute the bound formally, one collects all admissible

(13) |

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

(14) |

This start system has

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 -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].