Root Counts and Start Systems

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.

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

$\begin{displaymath} F({\bf x}) = \left\{ \begin{array} {rcl} \left( \left[ ... ...ha_1 x_1 + \alpha_2 x_2 + \alpha_3 & = & 0 \end{array} \right.\end{displaymath}$

(1)

The total degree D equals $3 \times 3 \times 1$ and overshoots the number of roots. For this problem we see that the components of the eigenvector occur linearly, whereas the degree of the eigenvalue equals two. By separating the unknowns in a partition Z, a 2-homogeneous Bézout number is obtained as follows

$\begin{displaymath} Z = \{ \{ \lambda \} , \{ x_1 , x_2 \} \} \quad \quad \left... ... \quad \quad B_Z = 2 \times 1 + 2 \times 1 + 0 \times 1 = 4 .\end{displaymath}$

(2)

The matrix contains the degrees of the polynomials w.r.t. the sets in Z. The Bézout number B_Z is computed as the generalized permanent of this matrix. This computation models the resolution of the following linear-product system

$\begin{displaymath} F^{(0)}({\bf x}) = \left\{ \begin{array} {rcl} \overbrace... ...a_1 x_1 + \alpha_2 x_2 + \alpha_3 & = & 0. \end{array} \right.\end{displaymath}$

(3)

Any random number generator will yield $\alpha$ -coefficients of the linear-product system $F^{(0)}({\bf x}) = {\bf 0}$ so that it has exactly four regular solutions. This leads to a homotopy with an optimal number of solution paths.

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.

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, ${\bf x} = {\bf y}^U$ abbreviates the substitution $(x_1,x_2) \leftarrow (y_1 y_2^{-1} , y_1^{-1} y_2^2)$ .

$\begin{displaymath} F({\bf x}) = \left\{ \begin{array} {r} x_1^2 x_2^1 - 1 = ... ...ay} {r} y_1 - 1 = 0 \\ y_1 y_2^2 - 1 = 0 \end{array} \right.\end{displaymath}$

(4)

We see that $F({\bf x}) = {\bf 0}$ has two regular solutions. Geometrically, we have computed the area of a parallelogram spanned by the origin, the points (2,1) and (4,3), and their sum. This area equals the determinant of the matrix that has in its columns the spanning vectors of the parallelogram. Multiplying by U triangulates this matrix:

$\begin{displaymath} \left[ \begin{array} {rr} 1 & -1 \\ -1 & 2 \end{array} \rig... ...\left[ \begin{array} {rr} 1 & 1 \\ 0 & 2 \end{array} \right] .\end{displaymath}$

(5)

As $\det(U) = 1$ , U is called unimodular and preserves volume. Consequently, the transformation ${\bf x} = {\bf y}^U$ does not change the number of solutions. Note that the total degree and 2-homogeneous Bézout number equal respectively 21 and 10.

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.

**Figure 1:** A regular triangulation of the Newton polytope of F with polyhedral homotopy $\widehat F$ .
$\begin{figure} \begin{center} \begin{picture} (450,140)(10,10) \put(122,80){\ve... ...]^T \quad \quad {\bf v}^{(2)} = [0,0,1]^T$}\end{picture}\end{center}\end{figure}$

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.

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 $\mbox{$C \! \! \! \rule[0.1ex]{0.05em}{1.25ex} \;$}\,^{m+p}$ . 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.

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:

$\begin{displaymath} \det(X\vert L_i) = 0, \quad \Longleftrightarrow \quad \det... ...41} & c^{(i)}_{42} \\ \end{array} \right) = 0, \quad i=1,2,3,4\end{displaymath}$

(6)

The special choice of coordinates so that L₁ is spanned by the first two and L₂ by the last two basis vectors admits the choice of local coordinates for the solution X. The best Bézout number for this system equals 6 and the mixed volume equals 4, whereas there are only two solutions.

**Figure 2:** In $\mbox{$I \! \! P$}^3$ two thick lines meet four given lines L₁, L₂, L₃, and L₄ in a point. At the left we see a special configuration and the general configuration is at the right.
$\begin{figure} \begin{center} \begin{picture} (400,120)(0,10) %\setcoordinatesy... ...3}} \put(86,55){\circle{3}}\end{picture} } \end{picture}\end{center}\end{figure}$

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.