next up previous contents
Next: The Principles of Polynomial Up: Polynomial Homotopies for dense, Previous: Introduction

Three Classes of Polynomial Systems

The classification in Table 1 is inspired by [44]. The dense class is closest to the common algebraic description, whereas the determinantal systems arise in enumerative geometry.


 
Table 1: Key words of the three classes of polynomial systems.
system model theory space
dense highest degrees Bézout ${\Bbb P}^n$ projective
sparse Newton polytopes Bernshtein $({\Bbb C}^*)^n$ toric
determinantal localization posets Schubert Gmr Grassmannian

 

For the vector of unknowns ${\bf x} = (x_1,x_2,\ldots,x_n)$and exponents ${\bf a} = (a_1,a_2,\ldots,a_n) \in {\Bbb N}^n$, denote ${\bf x}^{\bf a} = x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$. A polynomial system $P({\bf x}) = {\bf0}$ is given by $P = (p_1,p_2,\ldots,p_n)$, a tuple of polynomials $p_i \in {\Bbb C}[{\bf x}]$, $i = 1,2,\ldots,n$.

The complexity of a dense polynomial p is measured by its degree d:

\begin{displaymath}p({\bf x}) = \sum_{0 \leq a_1+a_2+\cdots+a_n \leq d}
c_{\bf a} {\bf x}^{\bf a}, \quad \quad d = \deg(p),
\end{displaymath} (1)

where at least one monomial of degree d should have a nonzero coefficient. The total degree D of a dense system P is $D = \prod_{i=1}^n \deg(p_i)$.

Theorem 2.1 (Bézout [15])   The system $P({\bf x}) = {\bf0}$ has no more than D isolated solutions, counted with multiplicities.

Consider for example

 \begin{displaymath}
P(x_1,x_2) =
\left\{
\begin{array}{r}
x_1^4 + x_1 x_2 + ...
...y} \right.
\quad {\rm with~total~degree}~D = 4 \times 4 = 16.
\end{displaymath} (2)

Although D = 16, this system has only eight solutions because of its sparse structure.


The support A of a sparse polynomial p collects all exponents of those monomials whose coefficients are nonzero. Since we allow negative exponents ( ${\bf a} \in {\Bbb Z}^n$), we restrict ${\bf x} \in ({\Bbb C}^*)^n$, ${\Bbb C}^* = {\Bbb C}\setminus \{ 0 \}$.

\begin{displaymath}p({\bf x}) = \sum_{{\bf a} \in A} c_{\bf a} {\bf x}^{\bf a}, ...
...not= 0, \quad
A \subset {\Bbb Z}^n, \quad \char93 A < \infty.
\end{displaymath} (3)

The Newton polytope Q of p is the convex hull of the support Aof p. We model the structure of a sparse system P by a tuple of Newton polytopes ${\cal Q} = (Q_1,Q_2,\ldots,Q_n)$, spanned by ${\cal A} = (A_1,A_2,\ldots,A_n)$, the so-called supports of P.

The volume of a positive linear combination of polytopes is a homogeneous polynomial in the multiplication factors. The coefficients are mixed volumes. For instance, for (Q1,Q2), we write:

 \begin{displaymath}
2!{\rm vol}_2(\lambda_1 Q_1 + \lambda_2 Q_2)
= V_2(Q_1,Q_1...
... V_2(Q_1,Q_2) \lambda_1 \lambda_2
+ V_2(Q_2,Q_2) \lambda_2^2,
\end{displaymath} (4)

normalizing $V_2(Q,Q) = 2! {\rm vol}_2(Q)$. For the Newton polytopes of the system (2): $2! {\rm vol}_2(\lambda_1 Q_1 + \lambda_2 Q_2) =
4 \lambda_1^2 + 2 \cdot 8 \lambda_1 \lambda_2 + 5 \lambda_2^2$. To interpret this we look at Figure 1 and see that multiplying P1 and P2 respectively by $\lambda_1$ and $\lambda_2$ changes their areas respectively with $\lambda_1^2$ and $\lambda_2^2$. The cells in the subdivision of Q1 + Q2 whose area is scaled by $\lambda_1 \lambda_2$ contribute to the mixed volume. So, for the example in (2), the root count is eight.


  
Figure 1: Newton polytopes Q1, Q2, a mixed subdivision of Q1 + Q2 with volumes.
\begin{figure}
\begin{center}
\centerline{\psfig{figure=psfmcc.ps}}
\end{center}\end{figure}

Theorem 2.2 (Bernshtein [7])   A system $P({\bf x}) = {\bf0}$ with Newton polytopes ${\cal Q}$ has no more than $V_n({\cal Q})$ isolated solutions in $({\Bbb C}^*)^n$, counted with multiplicities.

The mixed volume was nicknamed [13] as the BKK bound to honor Bernshtein [7], Kushnirenko [51], and Khovanskii [49].


For the third class of polynomial systems we consider a matrix [C | X]where $C \in {\Bbb C}^{(m+r) \times m}$ and $X \in {\Bbb C}^{(m+r) \times r}$respectively collect the coefficients and indeterminates. Laplace expansion of the maximal minors of [C | X] in m-by-m and r-by-r minors yields a determinantal polynomial

 \begin{displaymath}
p({\bf x}) = \sum_{\scriptsize\begin{array}{c} I \cup J = U...
...} } {\rm sign}(I,J) C[I] X[J],
\quad U = \{ 1,2,\ldots,m+r\},
\end{displaymath} (5)

where the summation runs over all distinct choices I of m elements of U. The partition $\{ I, J \}$ of U defines the permutation $U \mapsto (I,J)$with ${\rm sign}(I,J)$ its sign. The symbols C[I] and X[I] respectively represent coefficient minors and minors of indeterminates. Note that for more general intersection conditions, the matrices [C | X] are not necessarily square.

The vanishing of a polynomial as in (5) expresses the condition that the r-plane X meets a given m-plane nontrivially. The counting and finding of all figures that satisfy certain geometric conditions is the central theme of enumerative geometry. For example, consider the following.

Theorem 2.3 (Schubert [91])   Let $m,r \geq 2$. In  ${\Bbb C}^{m+r}$ there are

 \begin{displaymath}
d_{m,r} \quad = \quad
\frac{1! \, 2! \, 3! \cdots (r\!- \!...
...\! + \! 1)! \, (m \! + \! 2)!
\cdots(m \! + \! r \! - \! 1)!}
\end{displaymath} (6)

r-planes that nontrivially meet mr given m-planes in general position.

This root count dm,r is sharp compared to other root counts, see [98] and [114] for examples.

We can picture the simplest case, using the fact that 2-planes in ${\Bbb C}^4$represent lines in ${\Bbb P}^3$. In Figure 2 the positive real projective 3-space corresponds to the interior of the tetrahedron.


$\textstyle \parbox{5cm}{
\par \centerline{\psfig{figure=psfgrass.ps,width=5cm}}
\par ~~~~~Figure~2: $m = 2 = r$ .
\par \addtocounter{figure}{1}
\par }$ $\textstyle \parbox{10cm}{
\par \smallskip
\par In Figure~2, we see two thick l...
...specialization of
the solution $r$ -plane when the input is specialized.
\par }$


Algorithmic proofs for the above theorems consist in two steps. First we show how to construct a generic start system that has exactly as many regular solutions as the root count. Then we set up a homotopy for which all isolated solutions of any particular target system lie at the end of some solution path originating at some solution of the constructed start system.


next up previous contents
Next: The Principles of Polynomial Up: Polynomial Homotopies for dense, Previous: Introduction
Jan Verschelde
2001-04-08