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 x14 - c1 = 0 = x24 - c2, where c1 and c2 are randomly chosen complex numbers. Note that the computation of models the structure of the solutions of P(0) as four solutions for x1 crossed with four solutions for x2.
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 MZhas 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 BZ is the permanent of MZ.
(10) |
(11) |
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) |
(13) |
(14) |
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].