The computation of a root count is identified with the resolution of a generic system. In this sense, we call root-counting a symbolic computation mirroring this resolution. The basic root-counting principles for dense, sparse, and determinantal systems are exemplified next.

The use of multi-homogenization was proposed in [Morgan and Sommese 1987a,Morgan and Sommese 1987b]. Li, Sauer and Yorke [1987a, 1987b] introduced random product homotopies, see also [Li and Wang 1991].

**Example 3.1**

Consider a 2-dimensional generalized eigenvalue problem, represented by a polynomial in with as coefficients 2-by-2 matrices. A linear equation is added to scale the eigenvectors.

(1) |

(2) |

(3) |

A heuristic method developed for constructing a good partition *Z* of
the set of unknowns is outlined in [Verschelde 1996].
Besides that, an exhaustive enumeration as in [Wampler 1992] of all
partitions is available in PHC.
In case the number of independent roots equals *B*_{Z}, interpolation can
be used to construct a start
system [
Verschelde, Beckers, and Haegemans].

The idea of [Verschelde and Haegemans 1993] is that not every polynomial should be modeled by the same partition. This leads to partitioned linear-product start systems. General linear-product start systems were constructed in [Verschelde and Cools 1993b] and applied to symmetric polynomial systems in [Verschelde and Cools 1994]. The key condition is that a linear-product start system must contain all monomials of the target system. Theoretically, these homotopy methods can be considered as a special case of the polyhedral homotopy methods. In practice, we sometimes prefer product start systems, for solving a random linear-product system can be performed much more efficiently than solving a random coefficient system. PHC supports the construction of both partitioned and general linear-product start systems.

Efficient algorithms to construct general linear-product start systems are elaborated by Li, T. Wang and X. Wang [1996]. Morgan, Sommese and Wampler [1995] treated general product decompositions that do not restrict to linear factors. Recent coding efforts on partitioned linear-product start systems are reported by Wise, Sommese and Watson [1998].

The start solutions in linear-product homotopies are obtained by solving linear systems. In polyhedral homotopy methods [Huber and Sturmfels 1995] [Verschelde, Verlinden and Cools 1994 ], the start solutions are solutions to binomial systems.

**Example 3.2**

To solve a system that has two terms in any of its equations, unimodular transformations are applied to transform the system into a triangular structure. For the example below, abbreviates the substitution .

(4) |

(5) |

The above example is the sparsest case. The fewer monomials the fewer roots we expect [Khovanskii 1991]. In general, we apply Bernshtein's theorem [Bernshtein 1975] and count the number of roots by the mixed volume of the Newton polytopes. By means of a regular subdivision, polyhedral homotopies are constructed that start at systems corresponding to the cells in the subdivision. Figure 1 illustrates the case where all Newton polytopes are the same, which is the case of Kushnirenko's theorem [1976]. The root count is obtained as the volume of the Newton polytope shared by all polynomials in the system.

The program features four different lifting methods: implicit, static, dynamic, and symmetric lifting. Implicit lifting refers to the algorithms used in the proof of David Bernshtein [Bernshtein 1975]. The method in [Huber and Sturmfels 1995] is called static, to make the distinction with dynamic lifting, an algorithm that has been developed in [Verschelde, Gatermann, and Cools 1996] to construct regular triangulations of polytopes incrementally with low lifting values. Symmetric lifting was presented in [Verschelde and Gatermann 1995]. To construct regular subdivisions, both integer and floating-point lifting functions are available in PHC and elaborated with recursion. The Cayley trick [Gel'fand, Kapranov, and Zelevinsky 1994] defines in its polyhedral version [Sturmfels 1994] a polytope whose volume equals the mixed volume of the considered configuration of polytopes. In PHC, this trick is implemented by means of dynamic lifting. When many polynomials share the same exponents, this method is more efficient than static lifting.

With mixed volumes we restrict the counting to solutions that have all their components different from zero. Extensions to count and compute all isolated affine roots are described in [Rojas 1994,Rojas 1996], [Huber and Sturmfels 1997], [Li and Wang 1996], [Rojas and Wang 1996], [Gao, Li and Wang 1997], and in [Emiris and Verschelde 1997].

Gröbner and SAGBI bases translate questions concerning ideals and
subalgebras to monomial equations. The monomial orderings induced by
weight vectors provide recipes to set up homotopies that are flat
deformations, i.e.: preserve the structure of the solution set.
These are the key ideas for the Gröbner and SAGBI homotopies
introduced in
[Huber, Sottile and Sturmfels 1998]
to enumerate all *p*-planes that intersect *mp* given *m*-planes
in general position in .
See
[Ravi, Rosenthal and Wang 1996], [Rosenthal and Willems 1998],
for the relevance to the pole placement problem in control theory
and for related computational experiments see [Rosenthal and Sottile 1998] [Sottile 1998],
and [Verschelde 1998].
A third type of homotopies presented in [Sottile 1997]
and
[Huber, Sottile and Sturmfels 1998] has an
intrinsic geometric meaning and is briefly described next.

**Example 3.3**

A classical problem in enumerative geometry [Kleiman and Laksov 1972] deals with finding the two lines in projective 3-space that meet four given lines in general position. For the configurations as in Figure 2 we have to solve the following system:

(6) |

The so-called Pieri-homotopy starts at the special configuration, displayed at the left of Figure 2 and moves the third input line in general position. To reach the two solutions of this problem, it suffices to follow the solution paths defined by this homotopy.

The start systems and root counts presented here are optimal for three different classes of polynomial systems. This classification is only a sample and by no means exhaustive. We expect that future research developments will extend this list of root counters and homotopies.