\documentstyle[12pt,psfig]{amsart} % page format %\topmargin -10mm %\textwidth 168mm %\textheight 225mm %\oddsidemargin 0mm %\evensidemargin 0mm \headheight=8pt \topmargin=-15pt \textheight=634pt \textwidth=470pt \oddsidemargin=1pt \evensidemargin=1pt % some environments : \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}{Lemma}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{definition}{Definition}[section] \newtheorem{example}{Example}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{algorithm}{Algorithm}[section] % using AMS mathematical symbols \newcommand{\nn}{{\Bbb N}} \newcommand{\ee}{{\Bbb E}} \newcommand{\zz}{{\Bbb Z}} \newcommand{\rr}{{\Bbb R}} \newcommand{\cc}{{\Bbb C}} \newcommand{\pp}{{\Bbb P}} \def\qed{\hfill $\Box$} % end of proof \def\qex{\hfill \quad\vrule height1.2ex width0.5em depth 0pt} % end of example \begin{document} \bibliographystyle{plain} \title[Polynomial Homotopies for dense, sparse and determinantal Systems] {Polynomial Homotopies for dense, sparse \\ and determinantal Systems} \author{Jan Verschelde} \address{\hskip-\parindent Mathematical Sciences Research Institute \\ 1000 Centennial Drive \\ Berkeley, CA 94720-5070, U.S.A.} \address{\hskip-\parindent Department of Mathematics \\ Michigan State University \\ East Lansing, MI 48824-1027, U.S.A.} \email{jan@@msri.org, jan@@math.msu.edu or jan.verschelde@@na-net.ornl.gov, and urls: http://www.msri.org/people/members/jan http://www.mth.msu.edu/$\sim$jan} \thanks{Research at MSRI is supported in part by NSF grant DMS-9701755, benefited from a post-doctoral fellowship at MSRI and is also supported in part by NSF grant DMS-9804846 at MSU} \date{July 11, 1999} \begin{abstract} \noindent Numerical homotopy continuation methods for three classes of polynomial systems are presented. For a generic instance of the class, every path leads to a solution and the homotopy is optimal. The counting of the roots mirrors the resolution of a generic system that is used to start up the deformations. Software and applications are discussed. \bigskip \noindent {\bf AMS Subject Classification.} 14N10, 14M15, 52A39, 52B20, 52B55, 65H10, 68Q40. % 14N10 Enumerative problems (combinatorial problems) % 14M15 Grassmannian, Schubert varieties, flag manifolds % 52A39 Mixed volumes and related topics % 52B20 Lattice polytopes (including relations with commutative algebra % and algebraic geometry) % 52B55 computational aspects related to convexity % 65H10 Systems of nonlinear equations % 68Q40 Symbolic Computation, algebraic computation \bigskip \noindent {\bf Keywords}. polynomial system, numerical algebraic geometry, homotopy, continuation, deformation, path following, dense, sparse, determinantal, B\'ezout bound, Newton polytope, mixed volume, root count, enumerative geometry, numerical Schubert calculus. \end{abstract} \maketitle \tableofcontents \section{Introduction} Solving polynomial systems numerically means computing approximations to all isolated solutions. Homotopy continuation methods provide paths to approximate solutions. The idea is to break up the original system into simpler problems. To solve the original system, the solutions of the simpler systems are deformed into the solutions of the original problem. \medskip This paper presents optimal homotopies for three different classes of polynomial systems. Optimal means that for generic instances of the classes there are no diverging solution paths, whence the amount of computational work is linear in the number of solutions. In the next section we list the principal key words, definitions and main theorems for dense, sparse and determinantal polynomial systems. The proofs of these theorems follow from the correctness of the homotopies. \medskip Path-following methods are standard numerical techniques~(\cite{ag90,ag93,ag97}, \cite{mor87}, \cite{wat86,wat89}) to achieve global convergence when solving nonlinear systems. For polynomial systems we can reach all isolated solutions. In the third section we describe the paradigm of Cheater's homotopy~(\cite{lsy89},~\cite{lw92}) or coefficient-parameter polynomial continuation~(\cite{ms89},~\cite{ms90}). This paradigm allows to construct homotopies for which singularities only occur at the end of the paths. To deal with components of solutions we use an embedding method that leads to generic points on each component. This method is essential to numerical algebraic geometry~\cite{sw96}. \medskip From~\cite{kem93} we cite: ``Algebraic geometry studies the delicate balance between the geometrically plausible and the algebraically possible''. By a choice of coordinates we set up an algebraic formulation for a geometric problem that is then solved by automatic computations. While this approach is extremely powerful, we might get trapped into tedious wasted computations after loosing the original geometric meaning of the problem. In section four we stress the geometric intuition of homotopy methods. Compactifications and homogeneous coordinates provide us the tools to generate the numerically most favorable representations for the solutions to our problem. In section five we arrive at the heart of modern homotopy methods where we outline specific algorithms to implement the root counts\footnote{The term ``root count'' was coined by Canny and Rojas~\cite{cr91} while introducing mixed volumes to computational algebraic geometry.}. The counting of the roots mirrors the resolution of a system in generic position that is used as starting point in the deformations. \medskip Polyhedral methods occupy the central part of current research, as they are responsible for a computational breakthrough in numerical general-purpose solvers for polynomial systems. Section six is devoted to numerical software with an emphasis on the structure of the package PHC, developed by the author during the past decade. Another novel and exciting research development concerns the numerical Schubert calculus, which is one of the major new features in the second public release of~PHC. The author has gathered more than one hundred polynomial systems that arose in various application fields. This collection serves as a test suite for software and a gallery to demonstrate the importance of polynomial systems to mathematical modelling. In section seven we sample some interesting cases. \medskip The reference list contains a compilation of the most relevant technical contributions to polynomial homotopy continuation. Besides those we want to point at some other works in the literature that are of special interest. Some user-friendly introductions to algebraic geometry appeared in recent years: see~\cite{abh90}, \cite{fal90}, \cite{har95}, with computational aspects in~\cite{cls97} and~\cite{cls98}. As Newton polytopes have become extremely important, we recommend~\cite{zie95} and the handbook chapters~\cite{gr97}. See also~\cite{stu98} for the interplay between the combinatorics of polytopes and the (real) roots of polynomials. A recent survey that also covers polyhedral homotopies along with other polynomial continuation methods appeared in~\cite{li97}. \section{Three Classes of Polynomial Systems} The classification in Table~\ref{tabclasses} is inspired by~\cite{hss98}. The dense class is closest to the common algebraic description, whereas the determinantal systems arise in enumerative geometry. \begin{table}[ht] \begin{center} \begin{tabular}{|c||c|c|c|c|} \hline system & model & theory & \multicolumn{2}{c|}{space} \\ \hline \hline dense & highest degrees & B\'ezout & $\pp^n$ & projective \\ \hline sparse & Newton polytopes & Bernshte\v{\i}n & $(\cc^*)^n$ & toric \\ \hline determinantal & localization posets & Schubert & $G_{mr}$ & Grassmannian \\ \hline \end{tabular} \smallskip \caption{Key words of the three classes of polynomial systems.} \label{tabclasses} \end{center} \end{table} 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 \nn^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}) = {\bf 0}$ is given by $P = (p_1,p_2,\ldots,p_n)$, a tuple of polynomials $p_i \in \cc[{\bf x}]$, $i = 1,2,\ldots,n$. \smallskip The complexity of a {\em dense polynomial} $p$ is measured by its degree~$d$: \begin{equation} 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{equation} where at least one monomial of degree $d$ should have a nonzero coefficient. The {\em total degree} $D$ of a {\em dense system} $P$ is $D = \prod_{i=1}^n \deg(p_i)$. %\smallskip %The projective space $\pp^n$ provides a compactification of affine %space~$\cc^n$. \begin{theorem}(B\'ezout~{\rm \cite{cls97}}) The system $P({\bf x}) = {\bf 0}$ has no more than $D$ isolated solutions, counted with multiplicities. \end{theorem} Consider for example \begin{equation} \label{eqexsys} P(x_1,x_2) = \left\{ \begin{array}{r} x_1^4 + x_1 x_2 + 1 = 0 \\ x_1^3 x_2 + x_1 x_2^2 + 1 = 0 \end{array} \right. \quad {\rm with~total~degree}~D = 4 \times 4 = 16. \end{equation} Although $D = 16$, this system has only eight solutions because of its sparse structure. \medskip The {\em support} $A$ of a {\em sparse polynomial} $p$ collects all exponents of those monomials whose coefficients are nonzero. Since we allow negative exponents (${\bf a} \in \zz^n$), we restrict ${\bf x} \in (\cc^*)^n$, $\cc^* = \cc \setminus \{ 0 \}$. \begin{equation} p({\bf x}) = \sum_{{\bf a} \in A} c_{\bf a} {\bf x}^{\bf a}, \quad \quad \forall {\bf a} \in A: c_{\bf a} \not= 0, \quad A \subset \zz^n, \quad \#A < \infty. \end{equation} The {\em Newton polytope} $Q$ of~$p$ is the convex hull of the support~$A$ of~$p$. We model the structure of a {\em 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 {\em supports} of~$P$. \smallskip The volume of a positive linear combination of polytopes is a homogeneous polynomial in the multiplication factors. The coefficients are {\em mixed volumes}. For instance, for $(Q_1,Q_2)$, we write: \begin{equation} \label{eqvolpol} 2!{\rm vol}_2(\lambda_1 Q_1 + \lambda_2 Q_2) = V_2(Q_1,Q_1) \lambda_1^2 + 2 \cdot V_2(Q_1,Q_2) \lambda_1 \lambda_2 + V_2(Q_2,Q_2) \lambda_2^2, \end{equation} normalizing $V_2(Q,Q) = 2! {\rm vol}_2(Q)$. For the Newton polytopes of the system~(\ref{eqexsys}): $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~\ref{figmcc} and see that multiplying $P_1$ and $P_2$ 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 $Q_1 + Q_2$ whose area is scaled by $\lambda_1 \lambda_2$ contribute to the mixed volume. So, for the example in~(\ref{eqexsys}), the root count is eight. \begin{figure}[hbt] \begin{center} \centerline{\psfig{figure=psfmcc.ps}} \caption{Newton polytopes $Q_1$, $Q_2$, a mixed subdivision of $Q_1 + Q_2$ with volumes.} \label{figmcc} \end{center} \end{figure} \begin{theorem} (Bernshte\v{\i}n~{\rm \cite{ber75}}) A system $P({\bf x}) = {\bf 0}$ with Newton polytopes~${\cal Q}$ has no more than $V_n({\cal Q})$ isolated solutions in $(\cc^*)^n$, counted with multiplicities. \end{theorem} The mixed volume was nicknamed~\cite{cr91} as the BKK bound to honor Bernshte\v{\i}n~\cite{ber75}, Kushnirenko~\cite{kus76}, and Khovanski{\v{\i}}~\cite{kho78}. \medskip For the third class of polynomial systems we consider a matrix $[C | X]$ where $C \in \cc^{(m+r) \times m}$ and $X \in \cc^{(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 {\em determinantal} polynomial \begin{equation} \label{eqdetpol} p({\bf x}) = \sum_{\scriptsize \begin{array}{c} I \cup J = U \\ I \cap J = \emptyset \end{array} } {\rm sign}(I,J) C[I] X[J], \quad U = \{ 1,2,\ldots,m+r\}, \end{equation} 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. \smallskip The vanishing of a polynomial as in~(\ref{eqdetpol}) 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. \begin{theorem} (Schubert~{\rm \cite{sch1891}}) Let $m,r \geq 2$. In~$\cc^{m+r}$ there are \begin{equation} \label{eqgrassdeg} d_{m,r} \quad = \quad \frac{1! \, 2! \, 3! \cdots (r\!- \!2) ! \, (r \!-\!1)! \cdot (mr)!}{m!\, (m \! + \! 1)! \, (m \! + \! 2)! \cdots(m \! + \! r \! - \! 1)!} \end{equation} $r$-planes that nontrivially meet $mr$ given $m$-planes in general position. \end{theorem} This root count $d_{m,r}$ is sharp compared to other root counts, see~\cite{sot98} and~\cite{ver98} for examples. \smallskip We can picture the simplest case, using the fact that 2-planes in $\cc^4$ represent lines in $\pp^3$. In Figure~2 the positive real projective 3-space corresponds to the interior of the tetrahedron. \bigskip \parbox[b]{5cm}{ \centerline{\psfig{figure=psfgrass.ps,width=5cm}} ~~~~~Figure~2: $m = 2 = r$. \addtocounter{figure}{1} } \ \ \ \ \ \ \ \ \parbox[b]{10cm}{ \smallskip In Figure~2, we see two thick lines meeting four given skew fine lines in a point. When not all input planes have the same dimension, but when the number of solutions is still finite, Pieri's formula~\cite{pie1891} provides a root count~\cite{sot97a,sot97b}. \smallskip In~\cite{hss98} the problem is solved in chains of nested subspaces, using a cellation of the Grassmannian $G_{mr}$ of $r$-planes in $\cc^{m+r}$. A {\em localization poset} models~\cite{hv99} the specialization of the solution $r$-plane when the input is specialized. } \bigskip 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. \section{The Principles of Polynomial Homotopy Continuation Methods} Homotopy continuation methods operate in two stages. Firstly, homotopy methods exploit the structure of $P$ to find a root count and to construct a start system $P^{(0)}({\bf x}) = {\bf 0}$ that has exactly as many regular solutions as the root count. This start system is embedded in the {\em homotopy} \begin{equation} \label{eqlinhom} H({\bf x},t) = \gamma(1-t)P^{(0)}({\bf x}) + t P({\bf x}) = {\bf 0}, \quad t \in [0,1], \end{equation} with $\gamma \in \cc$ a random number. In the second stage, as $t$ moves from 0 to 1, numerical continuation methods trace the paths that originate at the solutions of the start system towards the solutions of the target system. \smallskip \noindent The good properties we expect from a homotopy $H({\bf x},t) = {\bf 0}$ are (borrowed from \cite{li97}): \begin{enumerate} \item ({\em triviality}) The solutions for~$t=0$ are trivial to find. \item ({\em smoothness}) No singularities along the solution paths occur. \item ({\em accessibility}) All isolated solutions can be reached. \end{enumerate} \bigskip Continuation or path-following methods are standard numerical techniques (\cite{ag90,ag93,ag97}, \cite{mor87}, \cite{wat86,wat89}) to trace the solution paths defined by the homotopy using {\em predictor-corrector} methods. The smoothness property of complex polynomial homotopies implies that paths never turn back, so that during correction the parameter $t$ stays fixed, which simplifies the set up of path trackers. A pseudo-code description of a path tracker is in Algorithm~\ref{algpathfoll}. \medskip The {\em predictor} delivers at each step of the method a new value for the continuation parameter and predicts an approximate solution of the corresponding new system in the homotopy. Figure~\ref{figsectan} shows two common predictor schemes. The predicted approximate solution is adjusted by applying Newton's method as {\em corrector}. The third ingredient in path-following methods is the {\em adaptive step size control}. The step length is determined to enforce quadratic convergence in the corrector to avoid path crossing. \medskip \begin{algorithm} \label{algpathfoll} {\rm Following one solution path by an increment-and-fix predictor-corrector method with an adaptive step size control strategy. \bigskip \noindent \begin{tabular}{lcr} Input: \ \ $H({\bf x},t)$, ${\bf x}^* \in \cc^n$: $H({\bf x}^*,0) = {\bf 0}$, & \ \ \ & {\em homotopy and start solution} \\ \ \ \ \ \ \ \ \ \ \ \ \ $\epsilon > 0$, $max\_it$, $max\_steps$. & & {\em accuracy and upper bounds} \\ Output: ${\bf x}^*$, success if $||H({\bf x}^*,1)|| \leq \epsilon$. & & {\em approximate solution if success} \\ \\ $t := 0$; \ $k := 0$; & & {\em initialization} \\ $h := max\_step\_size$; & & {\em step length} \\ $old\_t := t$; \ $old\_{\bf x}^* := {\bf x}^*$ & & {\em back up values for $t$ and ${\bf x}^*$ } \\ $previous\_{\bf x}^* := {\bf x}^*$; & & {\em previous approximate solution} \\ stop := false; & & {\em combines stopping criteria} \\ while $t < 1$ and not stop loop & & \\ \ \ \ $t := \min(1,t + h)$; & & {\em secant predictor for $t$} \\ \ \ \ ${\bf x}^* := {\bf x}^* + h ( {\bf x}^* - previous\_{\bf x}^* )$; & & {\em secant predictor for ${\bf x}^*$} \\ \ \ \ Newton($H({\bf x},t),{\bf x}^*,\epsilon,max\_it$,success); & & {\em correct with Newton's method} \\ \ \ \ if success & & {\em step size control} \\ \ \ \ \ then $h := \min(Expand(h),max\_step\_size)$; & & {\em enlarge step length} \\ \ \ \ \ \ \ \ \ \ \ \ $previous\_{\bf x}^* := old\_{\bf x}^*$; & & {\em go further along path} \\ \ \ \ \ \ \ \ \ \ \ \ $old\_t := t$; \ $old\_{\bf x}^* := {\bf x}^*$; & & {\em new back up values} \\ \ \ \ \ else \ $h := Shrink(h)$; & & {\em reduce step length} \\ \ \ \ \ \ \ \ \ \ \ \ $t := old\_t$; \ ${\bf x}^* := old\_{\bf x}^*$; & & {\em step back and try again} \\ \ \ \ end if; & & \\ \ \ \ $k := k+1$; & & {\em augment counter} \\ \ \ \ stop := ($h < min\_step\_size$) or ($k > max\_steps$); & & {\em stopping criteria} \\ end loop; & & \\ success := ($||H({\bf x}^*,1)|| \leq \epsilon$). & & {\em report success or failure} \end{tabular} } \end{algorithm} Following all paths can be done sequentially, one path at a time, or in parallel, with for each solution path the same sequence of values of the continuation parameter. The sequential path-following method has the advantage that the low overhead of communication~\cite{acw89} makes it very suitable to run on multi-processor environments. Note that the memory requirements are optimal. \begin{figure}[hbt] \begin{center} \centerline{\psfig{figure=psfsectan.ps}} \caption{The secant and tangent predictor with step length~$h$.} \label{figsectan} \end{center} \end{figure} \medskip To solve repeatedly a polynomial system with the same coefficient structure $P({\bf c},{\bf x}) = {\bf 0}$, the homotopy~(\ref{eqlinhom}) is applied with $P^{(0)} = P({\bf c}^0,{\bf x}) = {\bf 0}$ a system with random coefficients~${\bf c}^0$. Solving $P({\bf c}^0,{\bf x}) = {\bf 0}$ is no longer trivial, so the name {\em cheater's homotopy}~\cite{lsy89} is appropriate. A similar idea appeared in~\cite{ms89,ms90}. For coefficients given as functions of parameters, a refined version of cheater's homotopy in~\cite{lw92} avoids repeated evaluation of those functions during path following: \begin{equation} \label{eqnonlincheat} H({\bf x},t) = P((1-[t-t(1-t) \gamma]){\bf c}^0 + (t-t(1-t) \gamma){\bf c},{\bf x}) = {\bf 0}, \quad t \in [0,1], \gamma \in \cc. \end{equation} In~\cite{lw92} it is proven that with~(\ref{eqnonlincheat}) all isolated solutions of~$P({\bf c},{\bf x}) = {\bf 0}$ can be reached and that singularities can only occur at the end of the paths. \smallskip Typically, when using a cheater's homotopy, the computational effort spent towards the end of the paths often accounts for most of the work. The main numerical problem is then to distinguish irrelevant solutions at infinity from ill-conditioned but possibly meaningful solutions. End games~\cite{hv98}, \cite{msw91,msw92a,msw92b}, \cite{sws96} provide several procedures to approximate the winding number of a path. Recently, Zeuthen's rule was applied in~\cite{kss98} to determine numerically the multiplicity of an isolated solution. Multi-precision facilities are useful for evaluation of residuals and root refinement for badly scaled solutions. \medskip In most applications, the polynomial systems have real coefficients and invite the use of real homotopies. In~\cite{bm84} it was conjectured and proven in~\cite{lw93} that generically, real homotopies contain no singular points other than a finite number of quadratic turning points. At those bifurcation points pairs of real solution paths become imaginary or conversely, complex conjugated solution paths join to yield two real solution paths. We refer to~\cite{all84}, \cite{hk90}, \cite{li97} and~\cite{lw93,lw94} for a discussion of numerical techniques to deal with quadratic turning points. A remarkable application of real homotopies in the real world consists in the finding of the relevant parameters of a polynomial system to maximize the number of real roots, see~\cite{die98} for the 40 real solutions for the Stewart-Gough platform in mechanics. \medskip In~\cite{sw96} the use of homotopy continuation to deal with overdetermined and components of solutions is discussed. Geometrically one slices the components of solutions with as many random hyperplanes as the dimension of the components. The solutions to the original polynomial system augmented with these random linear equations for the hyperplanes are {\em generic points} of the components, constituting the main numerical data to study those components. In particular, the number of generic points one obtains by this slicing procedure equals the sum of the degrees over all top-dimensional components of solutions. \medskip To make the algorithms of~\cite{sw96} more efficient, in~\cite{sv99}, the following embedding of the polynomial system~$P({\bf x}) = {\bf 0}$ is proposed: \begin{equation} \label{eqembed} \left\{ \begin{array}{rl} p_i({\bf x}) + \lambda_i z = 0, & i=1,2,\ldots,n \\ {\displaystyle \sum_{j=1}^n c_j x_j + z = 0} \end{array} \right. \end{equation} where the $\lambda_i$'s and $c_j$'s are random complex numbers. This embedding has the advantage over the algorithms in~\cite{sw96} that fewer solution paths diverge. Solutions to the system~(\ref{eqembed}) with $z = 0$ lie on a component of solutions. By Bertini's theorem, all solutions with $z \not= 0$ are regular. In~\cite{sv99}, it is proven that those solutions can be used as start solutions to reach {\em all} isolated solutions of the original polynomial system~$P({\bf x}) = {\bf 0}$. \medskip The embedding~(\ref{eqembed}) is performed repeatedly in the routine `Embed' in the algorithm (copied from~\cite{sv99}) below. \begin{algorithm} \label{algcascade} {\rm Cascade of homotopies between embedded systems. \bigskip \begin{tabular}{lcr} Input: $P$, $n$. & & {\em system with solutions in $\cc^n$} \\ Output: $({\cal E}_i,{\cal X}_i,{\cal Z}_i)_{i=0}^n$. & & {\em embeddings with solutions} \\ \\ ${\cal E}_0 := P$; & & {\em initialize embedding sequence} \\ for $i$ from 1 up to $n$ do & & {\em slice and embed} \\ \ \ \ ${\cal E}_i$ := Embed(${\cal E}_{i-1},z_{i}$); & & {\em $z_i$ = new added variable} \\ end for; & & {\em homotopy sequence starts} \\ ${\cal Z}_n$ := Solve(${\cal E}_n$); & & {\em all roots are isolated, nonsingular, with $z_n \not= 0$}\\ for $i$ from $n-1$ down to 0 do & & {\em countdown of dimensions} \\ \ \ \ $H_{i+1}$ := $ t {\cal E}_{i+1} + (1-t)\left( \begin{array}{c} {\cal E}_i \\ z_{i+1} \end{array} \right) $; & & {\em \begin{tabular}{r} homotopy continuation \\ $t: 1 \rightarrow 0$ to remove $z_{i+1}$ \\ \end{tabular} } \hspace{-5mm} \\ \ \ \ ${\cal X}_i$ := limits of solutions of $H_{i+1}$ \\ \ \ \ \ \ \ as $t\to 0$ with $z_i=0$; & & {\em on component} \\ \ \ \ ${\cal Z}_i$ := $H_{i+1}({\bf x},z_{i} \not= 0,t=0)$; & & {\em not on component: these solutions} \\ & & {\em are isolated and nonsingular} \\ end for. & & \\ \end{tabular} } \end{algorithm} This embedding allows the efficient treatment of overdetermined systems and other nonproper intersections. By perturbing the added hyperplanes and extending the generic points by continuation, interpolation methods can lead to equations for the components. \section{The Geometry of the Deformations} Homotopy methods have an intuitive geometric interpretation. In this section we illustrate the geometry of the three types of moving into special position: product, toric, and Pieri deformations. These can be regarded as three applications of the principle of continuity or conservation of number in enumerative geometry. \smallskip Product homotopies deform polynomial equations into products of linear equations. In Figure~\ref{figbasic} we see the line configuration at the start and the ellipse-parabola intersection in the end. Note that complex space is the natural space for deformations. The other two complex conjugated intersection points could not be displayed in Figure~\ref{figbasic}. {\small \begin{figure}[hbt] \begin{center} \centerline{\psfig{figure=psfbasic.ps}} \caption{Intersection of quadrics: a degenerate and a target configuration.} \label{figbasic} \end{center} \end{figure} } \medskip The sparser a system, the easier it can be solved. In Figure~\ref{figincrpoco} we illustrate the idea of making a system sparser by setting up a so-called polyhedral homotopy that reduces this particular system at $t=0$ to a linear system. The lower hull of the Newton polytope of this homotopy induces a triangulation, which is used to count the roots. In particular, every cell in the triangulation gives rise to a homotopy with as many paths to follow as the volume of the cell. The other root for the example in Figure~\ref{figincrpoco} can be computed with a homotopy obtained from~$\widehat P$ by the substitution of variables $x_1 \leftarrow {\widetilde x}_1 t^{-1}$ and $x_2 \leftarrow {\widetilde x}_2 t^{-1}$. This transformation pushes the constant monomial up, so that at $t=0$ we have the nonconstant monomials in the start system to compute the other root. {\small \begin{figure}[hbt] \begin{center} \centerline{\psfig{figure=psfincrpoco.ps}} \caption{Triangulation of the Newton polytope of $P$ with polyhedral homotopy $\widehat P$.} \label{figincrpoco} \end{center} \end{figure} } \medskip Figure~\ref{figlines} displays a special and a general configuration of four lines. The basis has been chosen such that two of the four input lines are spanned by standard basis vectors. To compute all lines that meet four given lines, one of the four given lines is moved into special position so that it intersects two other given lines, see the left of Figure~\ref{figlines}. The solution lines must then originate at those two intersection points and reach to the other opposite line while meeting the line left in general position. \begin{figure}[hbt] \begin{center} \centerline{\psfig{figure=psflines.ps}} \caption{In $\pp^3$ two thick lines meet four given lines $L_1$, $L_2$, $L_3$, and $L_4$ in a point. At the left we see a special configuration and the general configuration is at the right.} \label{figlines} \end{center} \end{figure} \bigskip The constructions above are in a sense~\cite{abh90} ``heuristic proofs''. With the general position assumption we cheat a bit, avoiding the hard problem of assigning multiplicities. Making this so-called~\cite{wei62} ``method of degeneration'' rigorous was an important development in algebraic geometry. \bigskip To deal with solution paths diverging to ill-conditioned roots or to infinity we need to compactify our space. Instead of polynomials in $n$ variables we consider homogeneous forms with coordinates subject to equivalence relations. While mathematically all coordinate choices are equivalent, we select the numerically most favorable representations of the solutions. \medskip The usual projective transformation consists in the change of variables $x_i := \frac{z_i}{z_0}$, for $i=1,2,\ldots,n$, which leads to the homogeneous system $P({\bf z}) = {\bf 0}$. To have as many equations as unknowns, we add to this system a random hyperplane. Except for an algebraic set of the coefficients of this added hyperplane, all solution paths are guaranteed to stay inside $\cc^{n+1}$ when homotopy continuation is applied. We refer to~\cite{li97} for numerical techniques that dynamically restrict the computations to $n$ dimensions. \medskip For sparse polynomial systems, we introduce as in~\cite{ver99} a new variable for every facet of the Newton polytopes. The advantage of this more involved compactification is based on the observation that when paths diverge to infinity certain coefficients of the polynomial system become dominant. With toric homogenization the added variables that become zero identify the faces of the Newton polytopes for the parts of the system that become dominant. This compactification works in conjunction with polyhedral end games~\cite{hv98} which are summarized in Section~\ref{secsparhom}. \medskip The natural way to compactify $G_{mr}$ is to consider a multi-projective homogenization according to rows or columns of the matrix representations for the planes. In addition, we have that the planes are equivalent upon a linear change of basis. Choosing orthonormal matrices to represent the input planes leads to drastic improvements in the conditioning of the solution paths, see~\cite{hv99} and~\cite{ver98} for experimental data. \section{Root Counts and Start Systems} The main principle is that counting roots corresponds to solving start systems. Algorithms to illustrate this principle will be shown for little examples for the three classes of polynomial systems. \smallskip For dense polynomial systems, the computation of generalized permanents model the resolution of linear-product start systems. The algorithms to compute mixed volumes lead to polyhedral homotopies to solve sparse polynomial systems. The localization posets describe the structure of the cellation of the Grassmannian used to set up the Pieri deformations. \subsection{Dense Polynomials modeled by Highest Degrees} 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~\cite{li87} we see that B\'ezout'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. \medskip As the above presentation of B\'ezout's theorem suggests, the simplest cases are univariate and linear systems, which are used as start systems. For the example system~(\ref{eqexsys}), a start system~$P^{(0)}({\bf x}) = {\bf 0}$ 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 $D = 4 \times 4$ models the structure of the solutions of $P^{(0)}$ as four solutions for $x_1$ crossed with four solutions for~$x_2$. \medskip The earliest approaches of this homotopy appear in~\cite{cmy79}, \cite{dre77}, \cite{gz79}, \cite{gl80}, and were further developed in~\cite{li83}, \cite{mor83}, \cite{wri85}. The book~\cite{mor87} contains a very good introduction to the practice of solving polynomial system by homotopy continuation. Regularity results can be found in~\cite{ls87} and~\cite{zul88}. 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. \medskip Multi-homogeneous homotopies were introduced in~\cite{ms87a,ms87b} and applied to various problems in mechanism design, see e.g.~\cite{wms90,wms92a}. Similar are the random product homotopies~\cite{lsy87b,lsy87a}, applying intersection theory in~\cite{lw91}, but less suitable for automatic procedures. For our running example~(\ref{eqexsys}), we follow the approach of multi-homogenization and we group the unknowns according to the partition $Z = \{ \{ x_1 \} , \{ x_2 \} \}$. 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\'ezout bound $B_Z$ is the permanent of~$M_Z$. \begin{equation} \begin{array}{l} P(x_1,x_2) = \\ ~~~~~ \left\{ \begin{array}{r} x_1^4 + x_1 x_2 + 1 = 0 \\ x_1^3 x_2 + x_1 x_2^2 + 1 = 0 \end{array} \right. \end{array} \quad \begin{array}{rcc} M_Z & \! \! = \! \! & M_{\{ \{ x_1 \} , \{ x_2 \} \}} \\ & \! \! = \! \! & \left[ \begin{array}{cc} 4 & 1 \\ 3 & 2 \end{array} \right] \end{array} \quad \begin{array}{rcl} B_Z & \! \! = \! \! & {\rm per}(M_Z) \\ & \! \! = \! \! & 4 \times 2 + 3 \times 1 \\ & \! \! = \! \! & 11 \end{array} \end{equation} 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: \begin{equation} P^{(0)}({\bf x}) = \left\{ \begin{array}{c} {\displaystyle \prod_{i=1}^4 (x_1 - \alpha_{1i}) \prod_{i=1}^1 (x_2 - \beta_{1i})} = 0 \\ {\displaystyle \prod_{i=1}^3 (x_1 - \alpha_{2i}) \prod_{i=1}^2 (x_2 - \beta_{2i})} = 0 \\ \end{array} \right. \end{equation} In most applications the grouping of variables follows from their meaning, e.g.: for eigenvalue problems~$A {\bf x} = \lambda {\bf x}$, $Z = \{ \{ \lambda \} , \{ x_1, x_2 ,\ldots ,x_n \} \}$. Efficient permanent evaluations in conjunction with exhaustive searching algorithms for finding an optimal grouping were developed in~\cite{wam92}. In case the number of independent roots equals the B\'ezout bound, interpolation methods~\cite{vbh91} are useful. \medskip Partitioned linear-product start systems were developed in~\cite{vh93a} elaborating the idea that several different partitions can be used for the polynomials in the system. Motivated by symmetric applications~\cite{vc94a}, general linear-product start system were proposed in~\cite{vc93b}. 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. \begin{equation} S = \begin{array}{|c|} \hline \{ x_1 \} \{ x_1 , x_2 \} \{ x_1 \} \{ x_1 \} \\ \{ x_1 \} \{ x_1 , x_2 \} \{ x_1 \} \{ x_2 \} \\ \hline \end{array} \end{equation} To compute the bound formally, one collects all admissible $n$-tuples of sets, picking one set out of every row in the set structure. \begin{equation} \begin{array}{rl} B_S = & \! \! \! \! \# \{ ( \{ x_1 \} , \{ x_1 , x_2 \} ) , ( \{ x_1 \} , \{ x_2 \} ) , ( \{ x_1 , x_2 \} , \{ x_1 \} ) , \\ & ~~~ ( \{ x_1 , x_2 \} , \{ x_1, x_2 \} ) , ( \{ x_1 , x_2 \} , \{ x_1 \} ) , ( \{ x_1 , x_2 \} , \{ x_2 \} ) , \\ & ~~~ ( \{ x_1 \} , \{ x_2 \} ) , ( \{ x_1 , x_2 \} , \{ x_2 \} ) ( \{ x_1 \} , \{ x_2 \} ) ( \{ x_1 \} , \{ x_2 \} ) \} \end{array} \end{equation} Each admissible pair corresponds to a linear system that leads to a solution of a generic start system: \begin{equation} P^{(0)}({\bf x}) = \left\{ \begin{array}{c} (x_1+c_{11})(x_1+c_{12} x_2+c_{13})(x_1+c_{14})(x_1+c_{15}) = 0 \\ (x_1+c_{21})(x_1+c_{22} x_2+c_{23})(x_1+c_{24})(x_2+c_{25}) = 0 \\ \end{array} \right. \end{equation} This start system has $B_S = 10$ solutions. In~\cite{vc93b}, the following theorems were proven. \begin{theorem} Except for a choice of coefficients belonging to an algebraic set, there are exactly $B_S$ regular solutions to a random linear-product system based on the set structure~$S$. \end{theorem} The proof of the theorem consists in collecting the determinants that express the degeneracy conditions. These determinants are polynomials in the coefficients and vanish at an algebraic set. \medskip \begin{theorem} All isolated solutions to~$P({\bf x}) = {\bf 0}$ lie at the end of some solution path defined by a convex-linear homotopy originating at a solution of a random linear-product start system, based on a supporting set structure for~$P$. \end{theorem} The idea of the proof is to embed the homotopy into an appropriate projective space and to consider the projection of the discriminant variety as an algebraic set for the continuation parameter. See~\cite{lww96} for an alternative proof. \medskip A general approach to exploit product structures was developed in~\cite{msw95}. 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. \medskip The complexity of this homotopy based on the total degree is addressed in~\cite{bcss97} where $\alpha$-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~\cite{ds97}. \medskip 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~\cite{wam92}. With supporting set structures one may obtain a high success rate, see~\cite{lww96} for a efficient heuristic algorithm. Recent software extensions for finding optimal partitioned linear-product start systems are in~\cite{wsw98}. \subsection{Mixed Subdivisions of Newton Polytopes to compute Mixed Volumes} For~(\ref{eqexsys}), we collect the exponent vectors of the system $P$ in the supports $\cal A$: \begin{equation} \label{eqexpolysup} \begin{array}{l} P(x_1,x_2) = \\ ~~~~~ \left\{ \begin{array}{r} x_1^4 + x_1 x_2 + 1 = 0 \\ x_1^3 x_2 + x_1 x_2^2 + 1 = 0 \end{array} \right. \end{array} \quad \begin{array}{l} {\cal A} = (A_1,A_2) \\ ~~~~ A_1 = \{ (0,0) , (1,1) , (4,0) \} \\ ~~~~ A_2 = \{ (0,0) , (1,2) , (3,1) \} \end{array} \end{equation} The supports $A_1$ and $A_2$ span the respective Newton polytopes $Q_1$ and $Q_2$. \medskip The Cayley trick~\cite[Proposition 1.7, page 274]{gkz94} is a method to rewrite a certain resultant as a discriminant of one single polynomial with additional variables. The polyhedral version of this trick as in~\cite[Lemma 5.2]{stu94} is due to Bernd Sturmfels. It provides a one-to-one correspondence between the cells in a mixed subdivision and a triangulation of the so-called Cayley polytope spanned by the points of $A_i$ embedded in a $(2n-1)$-dimensional space. See~\cite{hrs99} for another application besides mixed-volume computation. As in~\cite{hrs99}, Figure~7 gives a ``one-picture proof'' of this trick, displaying the Cayley polytope for the supports~${\cal A}$ in~(\ref{eqexpolysup}). Note that this construction provides a definition for mixed subdivisions. \medskip \noindent~\parbox[t]{8cm}{ The Cayley polytope is spanned by the points in $A_1$, where each point of $A_1$ is extended with $n-1$ zero coordinates, and the points in $A_i$ where each point in $A_i$ is extended with the respective $i$-th standard basis vector, for $i=1,2,\ldots,n-1$. \smallskip Omitting the added coordinates of this Cayley embedding, every cell in a triangulation of the Cayley polytope is identified with a cell in a mixed subdivision of the original tuple of polytopes. We can see this identification geometrically when slicing the Cayley polytope with a hyperplane that separates the embedded polytopes. As in Figure~7, the slice contains $\lambda_1 Q_1 + \lambda_2 Q_2$ and the cells of a mixed subdivision are cut out by the cells in a triangulation of the Cayley polytope. }~\hspace{-0.3cm} \parbox[t]{10cm}{ \begin{center} \centerline{\psfig{figure=psfcayley.ps}} \medskip Figure~7 : Cayley polytope of $Q_1$ and $Q_2$. \addtocounter{figure}{1} \end{center} } \medskip The Cayley trick was implemented in~\cite{vgc96} as an application of the dynamic lifting algorithm to construct regular triangulations. This method calculates the volume polynomial~(\ref{eqvolpol}) completely. When one is only interested in the mixed volume, the method is only efficient when the supports do not differ much from each other. \medskip To compute only the mixed volume, the lift-and-prune approach was presented in~\cite{ec95}, using a primal model to prune in the tree of edge-edge combinations. This approach operates in two stages. First the polytopes are lifted by adding one coordinate to every point in the supports. In the second stage, one computes the facets of the lower hull of the Minkowski sum that are spanned by sums of edges. These facets constitute the {\em mixed cells} in a mixed subdivision. On the supports~$\cal A$ in~(\ref{eqexpolysup}), we consider the lifted supports \begin{equation} \label{eqlifted} {\widehat {\cal A}} = ({\widehat A}_1,{\widehat A}_2) \quad \begin{array}{l} {\widehat A}_1 = \{ (0,0,1) , (1,1,0) , (4,0,0) \} \\ {\widehat A}_2 = \{ (0,0,0) , (1,2,0) , (3,1,1) \} \end{array} \end{equation} The lower hulls of the lifted polytopes are displayed in Figure~\ref{fig3dmcc}. \medskip \begin{figure}[hbt] \begin{center} \centerline{\psfig{figure=psf3dmcc.ps}} \caption{Lifted polytopes ${\widehat Q}_1$, ${\widehat Q}_2$, and a regular mixed subdivision of ${\widehat Q}_1 + {\widehat Q}_2$.} \label{fig3dmcc} \end{center} \end{figure} The two cells that contribute to the mixed volume are identified by inner normals $\alpha$ and $\beta$ that satisfy systems of linear equations and inequalities: \smallskip \begin{equation} \label{eqdual} \begin{array}{l} \! \! \! \! \alpha = (0,0,1) \\ \left\{ \begin{array}{rcl} 4 \alpha_1 = \alpha_1 + \alpha_2 & < & 1 \\ \alpha_1 + 2 \alpha_2 = 0 & < & 3 \alpha_1 + \alpha_2 + 1 \end{array} \right. \end{array} \quad \quad \begin{array}{l} \! \! \! \! \beta = (2,-1,1) \\ \left\{ \begin{array}{rcl} \beta_1 + \beta_2 = 1 & < & 4 \beta_1 \\ \beta_1 + 2 \beta_2 = 0 & < & 3 \beta_1 + \beta_2 + 1 \end{array} \right. \end{array} \end{equation} \smallskip \noindent These systems express that the cells correspond to facets spanned by the sum of two edges on the lower hulls of ${\widehat Q}_1$ and ${\widehat Q}_2$ respectively. The lift-and-prune method with a dual version of the linear inequality constrains as in~(\ref{eqdual}) was elaborated in~\cite{vgc96}, exploiting the fact that several polynomials can share the same Newton polytope (see~\cite{hs95}) and with dimension reductions. \medskip The geometric dual construction to Figure~\ref{fig3dmcc} is displayed in Figure~\ref{figfans}. \begin{figure}[hbt] \begin{center} \centerline{\psfig{figure=psffans.ps}} \caption{On the left we see the projection of a regular mixed subdivision of ${\widehat Q}_1 + {\widehat Q}_2$. On the right, we have the dual construction with complexes ${\cal N}_{\vee}^{1}(Q_1)$ and ${\cal N}_{\vee}^{1}(Q_2)$ collecting the cones of all vectors normal to the edges on the lower hulls of ${\widehat Q}_1$ and ${\widehat Q}_2$ respectively. The intersection of the cones contain the normals to the mixed cells.} \label{figfans} \end{center} \end{figure} As in~\cite{hs95}, we assume that there are $r$ different Newton polytopes. Given a tuple of lifted point sets ${\widehat {\cal A}} = ( {\widehat A}_1, {\widehat A}_2, \ldots, {\widehat A}_r )$, any lifted cell ${\widehat {\cal C}}_{\bf v}$ of a regular subdivision can be characterized by its inner normal as \begin{equation} {\widehat {\cal C}}_{\bf v} = ( \partial_{\bf v} {\widehat A}_1, \partial_{\bf v} {\widehat A}_2, \ldots , \partial_{\bf v} {\widehat A}_r ). \end{equation} Since ${\rm conv}({\widehat C}_{\bf v}) = {\rm conv}(\sum_{i=1}^r \partial_{\bf v} {\widehat A}_i)$ is a facet of the lower hull, the inner product $\langle . , {\bf v} \rangle$ attains \\[1mm] its minimum over ${\widehat A}_i$ at $\partial_{\bf v} {\widehat A}_i$, i.e., \begin{equation} \label{equa} \forall {\widehat {\bf a}}, {\widehat {\bf b}} \in \partial_{\bf v} {\widehat A}_i: \ \langle {\widehat {\bf a}} , {\bf v} \rangle = \langle {\widehat {\bf b}} , {\bf v} \rangle, \quad i = 1,2,\ldots,r, \end{equation} \begin{equation} \label{inequa} \forall {\widehat {\bf a}} \in {\widehat A}_i \setminus \partial_{\bf v} {\widehat A}_i, \ \forall {\widehat {\bf b}} \in \partial_{\bf v} {\widehat A}_i: \ \langle {\widehat {\bf a}} , {\bf v} \rangle > \langle {\widehat {\bf b}} , {\bf v} \rangle, \quad i = 1,2,\ldots,r. \end{equation} Algorithm~\ref{algshafac} (presented in~\cite{vgc96}) gives a way to compute all mixed cells by searching for feasible solutions to the constraints~(\ref{equa}) and~(\ref{inequa}). The algorithm generates a tree of all possible combinations of $k_i$-faces, with feasibility tests to prune branches that do not lead to mixed cells. The order of enumeration is organized so that mixed cells which share some faces also share a part of the factorization work to be done to solve the system defined by~(\ref{equa}). \begin{algorithm} \label{algshafac} {\rm Pruning algorithm with shared factorizations subject to inequality constraints: \begin{center} \begin{tabular}{lcr} Input: $({\widehat A}_1,{\widehat A}_2, \ldots, {\widehat A}_r)$, & & {\em lifted point sets} \ \\ \ \ \ \ \ \ \ \ \ $\!$ ${\bf k} = (k_1,k_2,\ldots,k_r)$, $n = \sum_{i=1}^r k_i$, & & {\em $A_i$ appears $k_i$ times } \ \\ \ \ \ \ \ \ \ \ \ $\!$ $({\widehat {\cal F}}_1,{\widehat {\cal F}}_2, \ldots, {\widehat {\cal F}}_r)$. & \ \ & {\em $k_i$-faces of lower hull of ${\rm conv}({\widehat A}_i)$} \ \\ Output: ${\widehat {\frak S}_\omega} = \{ \ {\widehat {\cal C}} \in {\widehat S}_\omega \ | \ V_n({\cal C},{\bf k}) > 0 \ \}$. & & {\em collection of lifted mixed cells} \ \\ \\ {\bf At level} $i$, $1 \leq i < r$: & & \\ \ \ {\em DATA and INVARIANT CONDITIONS}: & & \\ \ \ \ \ \ $\!$ $(M_1,\kappa)$: \ \ $M_1 {\bf v} = {\bf 0} \not\Rightarrow v_{n+1} = 0$, $\kappa = {\displaystyle \sum_{j=1}^{i-1} k_j}$ & & \begin{tabular}{r} {\em equalities} (\ref{equa}) \\ {\em upper triangular up to row $\kappa$} \end{tabular} \\ \ \ \ \ \begin{tabular}{ll} $(M_2,\kappa)$: & $M_2 {\bf v} \geq {\bf 0} \not\Rightarrow -v_{n+1} \geq 0$ \\ & $\dim(M_2) = n-\kappa$ \end{tabular} & & \begin{tabular}{r} {\em inequalities} (\ref{inequa}) \\ {\em still feasible and reduced} \end{tabular} \\ \ \ {\em ALGORITHM}: & & \\ \ \ \ \ \ for each ${\widehat C}_i \in {\widehat {\cal F}}_i$ loop & & {\em enumerate over all $k_i$-faces} \ \\ \ \ \ \ \ \ \ {\em Triangulate}$(M_1,\kappa,{\widehat C}_i)$; & & {\em ensure invariant conditions} \ \\ \ \ \ \ \ \ \ if $M_1 {\bf v} = {\bf 0} \not\Rightarrow v_{n+1} = 0$ & & {\em test for feasibility w.r.t.} (\ref{equa}) \ \\ \ \ \ \ \ \ \ \ then {\em Eliminate}$(M_1,M_2,\kappa,{\widehat C}_i, {\widehat A}_i)$; & & {\em eliminate unknowns} \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ if $M_2 {\bf v} \geq {\bf 0} \not\Rightarrow -v_{n+1} \geq 0$ & & {\em test for feasibility w.r.t.} (\ref{inequa}) \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ then proceed to next level $i+1$; & & \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ end if; & & \\ \ \ \ \ \ \ \ end if; & & \\ \ \ \ \ \ end for. & & \\ {\bf At level} $i=r$: & & \\ \ \ Compute $\bf v$: $M_1 {\bf v} = {\bf 0}$; & & \\ \ \ Merge the new cell ${\cal C}_{\bf v}$ with the list ${\widehat {\frak S}_\omega}$. & & \end{tabular} \end{center} } \end{algorithm} Note that (\ref{inequa}) has to be weakened to $\geq$ type inequalities in order to be able to compute also subdivisions that are not fine. This also explains the merge operation at the end. The feasibility tests in the algorithm allow an efficient computation of the mixed cells. The conditions~(\ref{equa}) and~(\ref{inequa}) are verified incrementally. After choosing a $k_i$-face ${\widehat C}_i = \{ {\widehat {\bf c}}_{0i}, {\widehat {\bf c}}_{1i} , \ldots , {\widehat {\bf c}}_{k_i i} \}$ of ${\widehat A}_i$, linear programming is used to check whether $({\widehat C}_1, \ldots , {\widehat C}_i )$ can lead to a mixed cell in the induced subdivision. \medskip We end this section with complexity results. The complexity of computing mixed volumes is proven~\cite{dgh98} to be $\#P$-hard. This complexity class is typical for all enumerative problems, since, unlike the class $NP$, there exists no algorithm that runs in polynomial time for arbitrary dimensions to verify that a guessed answer is correct. Although the current algorithmical practice suggests that computing mixed volumes is harder than computing volumes of polytopes (which is also known as a $\#P$-hard problem~\cite{df88}), this is not the case from a complexity point of view as shown in~\cite{dgh98}. In~\cite{emi96} it is shown that the mixed volume~$V_n({\cal Q})$ is bounded from below by $n! {\rm vol}_n(Q_\mu)$, $Q_\mu$ being the polytope of minimum volume in~$\cal Q$. \subsection{Sparse Polynomial Systems solved by Polyhedral Homotopies} \label{secsparhom} The simplest system in the polytope model that still has isolated solutions in~$(\cc^*)^n$ has exactly two terms in every equation. Polyhedral homotopies~\cite{hs95} solve systems with random complex coefficients starting from sparser subsystems. For~(\ref{eqexsys}), the homotopy with supports~$\widehat {\cal A}$ as in~(\ref{eqlifted}) is \begin{equation} \label{eqexpolyhom} {\widehat P}(x_1,x_2,t) = \left\{ \begin{array}{r} c_1 x_1^4 t^0 + c_2 x_1 x_2 t^0 + c_3 t^1 = 0 \\ c'_1 x_1^3 x_2 t^1 + c'_2 x_1 x_2^2 t^0 + c'_3 t^0 = 0 \end{array} \right. \quad {\rm with~} c_i,c'_i \in \cc^*. \end{equation} The exponents of~$t$ are the values of the lifting~$\omega$ applied to the supports. \medskip To find the start systems, we look at Figure~\ref{fig3dmcc}, at the subdivision that is induced by this lifting process. The start systems have Newton polytopes spanned by one edge of the first and one edge of the second polytope. Since the two cells that contribute to the mixed volume are characterized by their inner normals $\alpha$ and $\beta$ satisfying~(\ref{eqdual}) we denote the start systems respectively by $P^\alpha$ and $P^\beta$. To compute start solutions, unimodular transformations make the system triangular as follows. After dividing the equations so that the constant term is present, we apply the substitution $x_1 = y_2$, $x_2 = y_1^{-1} y_2^3$ on $P^\alpha$ as follows: \begin{equation} \label{eqbin} P^{\alpha}({\bf x}) = \left\{ \begin{array}{r} x_1^3 x_2^{-1} + c''_1 = 0 \\ x_1 x_2^2 + c''_2 = 0 \end{array} \right. \quad P^{\alpha}({\bf x} = {\bf y}^U) = \left\{ \begin{array}{r} y_1 + c''_1 = 0 \\ y_1^{-2} y_2^7 + c''_2 = 0 \end{array} \right. \end{equation} \noindent The substitution in (\ref{eqbin}) is apparent in the notation (as used in~\cite{li97}) ${\bf x}^V = ({\bf y}^U)^V = {\bf y}^{VU} = {\bf y}^L$ elaborated as \begin{equation} \begin{array}{rcl} \left( \begin{array}{c} x_1^3 \cdot x_2^{-1} \\ x_1^1 \cdot x_2^2 \end{array} \right) & = & \left( \begin{array}{c} (y_1^0 y_2^1)^3 \cdot (y_1^{-1} y_2^3)^{-1} \\ (y_1^0 y_2^1)^1 \cdot (y_1^{-1} y_2^3)^2 \end{array} \right) \\ & = & \left( \begin{array}{c} y_1^{3 \cdot 0 - 1 \cdot (-1)} \cdot y_2^{3 \cdot 1 - 1 \cdot 3} \\ y_1^{1 \cdot 0 + 2 \cdot (-1)} \cdot y_2^{1 \cdot 1 + 2 \cdot 3} \end{array} \right) = \left( \begin{array}{c} y_1^1 \cdot y_2^0 \\ y_1^{-2} \cdot y_2^7 \end{array} \right). \end{array} \end{equation} The exponents are calculated by the factorization $VU = L$: \begin{equation} \left[ \begin{array}{rr} 3 & -1 \\ 1 & 2 \end{array} \right] \left[ \begin{array}{rr} 0 & 1 \\ -1 & 3 \end{array} \right] = \left[ \begin{array}{rr} 1 & 0 \\ -2 & 7 \end{array} \right] . \end{equation} Since $\det(U) = 1$, the matrix $U$ is called unimodular. \medskip The polyhedral homotopy~(\ref{eqexpolyhom}) directly extends the solutions of $P^{\alpha}$ to the target system. To obtain a homotopy starting at the solutions of~$P^{\beta}$, we substitute in~(\ref{eqexpolyhom}) $x_1 \leftarrow {\widetilde x}_1 t^{\beta_1}$, $x_2 \leftarrow {\widetilde x}_2 t^{\beta_2}$ and clear out the lowest powers of~$t$. This construction appeared in~\cite{hs95} and provides an algorithmic proof of the following theorem. \begin{theorem} \label{theobera} (Bernshte\v{\i}n~{\rm \cite[Theorem A]{ber75}}) For a general choice of coefficients for~$P$, the system $P({\bf x}) = {\bf 0}$ has exactly as many regular solutions as its mixed volume~$V_n({\cal Q})$. \end{theorem} The original algorithm Bernshte\v{\i}n used in his proof was implemented in~\cite{vvc94}. \medskip For the numerical stability of polyhedral continuation, it is important to have subdivisions induced by low lifting values, since those influence the power of the continuation parameter. In~\cite{vgc96} explicit lower bounds on integer lifting values were derived, but unfortunately the dynamic lifting algorithm does not generalize that well~\cite{lw98} if one is only interested in the mixed cells of a mixed subdivision. A balancing method was proposed in~\cite{glvw98} to improve the stability of homotopies induced by random floating-point lifting values. \medskip Once all solutions to a polynomial system with randomly generated coefficients are computed, we use cheater's homotopy to solve any specific system with the same Newton polytopes. One could say that polyhedral homotopies have removed the cheating part. The main advantage of polyhedral methods is that the mixed volume is a much sharper root count in most applications, leading to fewer paths to trace. They also allow more flexibility to exploit symmetry as demonstrated in~\cite{vg95}. \medskip In case the system has fewer isolated solutions than the mixed volume, we consider the face systems. Define the face of a polynomial $p$ with support $A$ as follows: \begin{equation} p({\bf x}) = \sum_{{\bf a} \in A} c_{\bf a} {\bf x}^{\bf a} \quad \mbox{has faces} \quad \partial_{\bf v} p({\bf x}) = \sum_{{\bf a} \in \partial_{\bf v} A} c_{\bf a} {\bf x}^{\bf a} \quad \mbox{for } {\bf v} \not= {\bf 0}. \end{equation} For ${\bf v} \not= {\bf 0}$, the corresponding face system of $P$ is $\partial_{\bf v} P = ( \partial_{\bf v} p_1, \partial_{\bf v} p_2, \ldots , \partial_{\bf v} p_n )$. \begin{theorem} \label{theoberb} (Bernshte\v{\i}n~{\rm \cite[Theorem B]{ber75}}) Suppose $V_n({\cal Q}) > 0$. Then, $P({\bf x}) = {\bf 0}$ has fewer than~$V_n({\cal Q})$ isolated solutions if and only if $\partial_{\bf v} P({\bf x}) = {\bf 0}$ has a solution in $(\cc^*)^n$, for~${\bf v} \not= {\bf 0}$. \end{theorem} As is the case for our running example~(\ref{eqexsys}), the Newton polytopes may be in generic position such that for any nonzero choice of the coefficients, the system has exactly as many isolated solutions as the mixed volume. In practical applications however, how can we decide whether paths are really going towards infinity? Relying on the actual computed values is arbitrarily, because $10^4$ is as far from infinity as~$10^8$, so we need algebraic structural data to certify the divergence. \medskip In the polyhedral end game~\cite{hv98} solution paths are represented by power series expansions: \begin{equation} \label{eqpower} \left\{ \begin{array}{rcl} x_i(s) & = & a_i s^{v_i} ( 1 + O(s) ) \\ t(s) & = & 1 - s^m \end{array} \right. \quad \quad t \approx 1, \quad s \approx 0. \end{equation} The winding number $m$ is lower than or equal to the multiplicity of the solution. For a solution diverging to infinity or to a zero-component solution we observe that $v_i \not= 0$. According to Theorem~\ref{theoberb}, this solution vanishes at a face system $\partial_{\bf v} P$ (same ${\bf v}$ with components $v_i$ as in~(\ref{eqpower})), certifying the divergence. \medskip To check whether a solution path really diverges is equivalent to the test on the value for~$v_i$. A first-order approximation of $v_i$ can be computed by \begin{equation} \frac{\log|x_i(s_1)| - \log|x_i(s_0)|}{\log(s_1) - \log(s_0)} = v_i + O(s_0), \end{equation} with $0 < s_1 < s_0$. The above formula assumes the correct value for~$m$. To compute $m$, solution paths are sampled geometrically with ratio $h$ as $s_k = h^{k/m} s_0$. The errors on the estimates for~$v_i$ are \begin{eqnarray} e_i^{(k)} & = & (\log|x_i(s_k)| - \log|x_i(s_{k+1})|) - (\log|x_i(s_{k+1})| - \log|x_i(s_{k+2})|) \\ & = & c_1 h^{k/m} s_0 (1 + O(h^{k/m})). \end{eqnarray} An estimate for~$m$ is derived from two consecutive errors~$e_i^{(k)}$. Extrapolation improves this estimate. So, by an inexpensive side calculation at the end of the paths, we obtain important structural algebraic information about the system. \medskip Recall that $V_n({\cal Q})$ count the roots in~$(\cc^*)^n$. Using Newton polytopes to count affine roots (i.e.: in~$\cc^n$ instead of~$(\cc^*)^n$) was proposed in~\cite{roj94} with the notion of shadowed polytopes obtained by the substitution $x_i \leftarrow x_i + c_i$ for arbitrary constants $c_i$. To arrive at sharper bounds, it suffices (see~\cite{lw96} and~\cite{rw96}) to add a random constant to every equation. Stable mixed volumes~\cite{hs97} provide a generically sharp affine root count. The constructions in~\cite{ev99} and~\cite{glw98} avoid the use of recursive liftings to compute stable mixed volumes. Further developments and generalizations can be found in~\cite{roj99}. \subsection{Determinantal Polynomials arising in Enumerative Geometry} Homotopies for solving problems in enumerative geometry appeared in~\cite{hss98}. The algorithms in the numerical Schubert calculus originated from questions in real enumerative geometry~\cite{sot97a,sot97b} and have their main application to the pole placement problem~\cite{byr89}, \cite{rrw96,rrw98}, \cite{ros94}, \cite{rw99} in control theory. \medskip The enumerative problems are formalized in some ``finiteness'' theorems, avoiding the explicit but involved (as in~(\ref{eqgrassdeg})) formulas for the root counts. \begin{theorem} \label{theoprob1} The number of $r$-planes meeting $mr$ general $m$-planes in~$\cc^{m+r}$ is a finite constant. \end{theorem} The first homotopy presented in~\cite{hss98} uses a Gr\"obner basis for the ideal that defines $G_{mr}$, as is derived in~\cite{stu93}. By Gr\"obner bases questions concerning any polynomial system are solved by relation to monomial equations. Every Gr\"obner basis defines a flat deformation, which preserves the structure of the solution set~\cite{eis95}. Geometrically, this type of deformation is used to collapse the solution set in projective space to the coordinate hyperplanes, or in the opposite direction, to extend the solutions of the monomial equations to those of the original system. The flat deformations that are obtained in this way are similar to toric deformations in the sense that one moves from the solutions of a subsystem to the solutions of the whole system. \medskip The Gr\"obner homotopies of~\cite{hss98} work in the synthetic Pl\"ucker embedding, and need to take the large set of defining equations of $G_{mr}$ into account. When expanding the minors into local coordinates, these equations are automatically satisfied, which leads to a much smaller polynomial system. Consequently, the second type of homotopies of~\cite{hss98}, the so-called SAGBI homotopies are more efficient. Instead of an ideal, we now have a subalgebra and work with a SAGBI basis, i.e.: the Subalgebra Analogue to a Gr\"obner Basis for an Ideal. The term order selects the monomials on the diagonal as the dominant ones. This implies that in the flat deformation (see~\cite{stu96} for a general description) only the diagonal monomials remain at~$t=0$. \medskip For $m=2=r$, the equations of the SAGBI homotopy in determinantal form are \begin{equation} \label{eqsabi22det} p_i({\bf x}) = \det \left[ \left. \begin{array}{cc} c_{11}^{(i)} & c_{12}^{(i)} \\ c_{21}^{(i)} & c_{22}^{(i)} \\ c_{31}^{(i)} & c_{32}^{(i)} \\ c_{41}^{(i)} & c_{42}^{(i)} \\ \end{array} \right| \begin{array}{cc} x_{11} ~ & x_{12} \\ x_{21} t & x_{22} \\ 1 & 0 \\ 0 & 1 \\ \end{array} \right] = 0, \quad i=1,2,3,4, \end{equation} where the coefficients $c_{kl}^{(i)}$ are random complex constants. In expanding the minors of~(\ref{eqsabi22det}), the lowest power of $t$ is divided out, minor per minor. The system at $t=0$ is solved by polyhedral continuation. The system at $t=1$ serves as start system in the cheater's homotopy to solve any system with particular real values for the coefficients~$c_{kl}^{(i)}$. Figure~\ref{figsagbi} outlines the structure of the general solver. {\small \begin{figure}[hbt] \begin{center} \begin{picture}(400,40)(0,0) \put(0,0){\framebox(50,40)[c] {\begin{tabular}{c} Binomial \\Systems \end{tabular}}} \put(60,20){\vector(1,0){50}} \put(60,25){polyhedral} \put(62,10){homotopy} \put(120,0){\framebox(50,40)[c] {\begin{tabular}{c} Generic \\ Complex \\ System \end{tabular}}} \put(180,20){\vector(1,0){40}} \put(189,25){flat} \put(183,10){deform.} \put(230,0){\framebox(50,40)[c] {\begin{tabular}{c} Generic \\ Complex \\ Problem \end{tabular}}} \put(290,20){\vector(1,0){50}} \put(293,25){cheater's} \put(292,10){homotopy} \put(350,0){\framebox(50,40)[c] {\begin{tabular}{c} Specific \\ Real \\ Problem \end{tabular}}} \end{picture} \caption{The SAGBI homotopy is at the center of the concatenation.} \label{figsagbi} \end{center} \end{figure} } SAGBI homotopies have been implemented~\cite{ver98} to verify some large instances of input planes for which it was conjectured that all solution planes would be real. We refer to~\cite{rs98} and \cite{sot98} for related work on these conjectures. In~\cite{sot99b} an asymptotic choice of inputs is generated for which all solutions are proven to be real. \medskip The third type of homotopies presented in~\cite{hss98} are the so-called Pieri homotopies. Since they are closer to the intrinsic geometric nature, they are applicable to a broader class of problems. In particular, we obtain an effective proof for the following. \begin{theorem} \label{theoprob2} The number of $r$-planes meeting $n$ general $(m+1-k_i)$-planes in~$\cc^{m+r}$, with $k_1 + k_2 + \cdots + k_n = mr$, is a finite constant. \end{theorem} Note that when all $k_i = 1$, we arrive at Theorem~\ref{theoprob1}. For general $k_i \not= 1$, we are not aware of any explicit formulas for the number of roots. \medskip Figure~\ref{figcelldeco} shows a part of a cellular decomposition of $G_{22}$ with the determinantal equations. We specialize the pattern~$X$ that represents a solution line by setting some of its coordinates to zero. This specialization determines a specialization of the input lines as follows: take those basis vectors not indexed by rows of~$X$ where zeroes have been introduced. The special line $S_X$ for this example is as in~(\ref{eqpierihom}) spanned by the first and third standard basis vector. \begin{figure}[hbt] \begin{center} \begin{picture}(240,120)(20,-10) \thicklines \put(-50,85){\small ${\rm det}\left[ S_X \left| \begin{array}{cc} x_{11} & 0 \\ 0 & 0 \\ 0 & x_{32} \\ 0 & x_{42} \\ \end{array} \right. \right] = 0$} \put(140,85){\small ${\rm det}\left[ S_X \left| \begin{array}{cc} x_{11} & 0 \\ x_{21} & 0 \\ 0 & x_{32} \\ 0 & 0 \\ \end{array} \right. \right] = 0$} \put(110,50){\line(4,1){40}} \put(90,50){\line(-4,1){40}} \put(10,15){\small ${\rm det}[L_3 | X] = {\rm det}\left[ L_3 \left| \begin{array}{cc} x_{11} & 0 \\ x_{21} & 0 \\ 0 & x_{32} \\ 0 & x_{42} \\ \end{array} \right. \right] = 0$} \put(260,10){[2~4]} \put(227,30){[1~4]} \put(293,30){[2~3]} \put(257,18){\line(-2,1){10}} \put(285,18){\line(2,1){10}} \end{picture} \caption{Part of a cellular decomposition of the Grassmannian of all 2-planes. At the right we have the short-hand notation with brackets. The bracket~$[2~4]$ contains the row indices to the lowest nonzero entries in~$X$. } \label{figcelldeco} \end{center} \end{figure} \medskip Figure~\ref{figcelldeco} pictures patterns of the moving 2-planes in the Pieri homotopy algorithm for the case $(m,r) = (2,2)$, see Figure~\ref{figlines}. The bottom matrix is the general representation of a solution that intersects already the two input lines spanned by the standard basis vectors. At the leaves of the tree by linear algebra operations we can intersect with a third input line. Moving down the poset, we deform form the left configuration in Figure~\ref{figlines} to the general problem. \medskip Denote by $L_1$ and $L_2$ the lines already met by $X$. At the leaves of the tree in Figure~\ref{figcelldeco} we intersect with the fourth line $L_4$. The special position for the third line $L_3$ is represented by the matrix $S_X$, which intersects any $X$ with coordinates as at the leaves of the tree. In the homotopy $H(X,t) = {\bf 0}$ we deform the line spanned by the columns of $S_X$ to line $L_3$, for $t = 0$ to $t = 1$. \begin{equation} \label{eqpierihom} S_X = \left[ \begin{array}{cc} 1 & 0 \\ 0 & 0 \\ 0 & 1 \\ 0 & 0 \\ \end{array} \right] \quad \quad H(X,t) = \left\{ \begin{array}{l} \det( L_4 | X ) = 0 \\ \det( (1-t) S_X + tL_3 | X ) = 0 \\ \end{array} \right. \quad t \in [0,1]. \end{equation} Every solution $X(t)$ of $H(X(t),t) = {\bf 0}$ intersects already three lines: $L_1$, $L_2$ and $L_3$. At the end, for $t=1$, $X$ also meets the line~$L_3$ in a point. \medskip The homotopy~(\ref{eqpierihom}) deforms two solution lines, starting at patterns which have their row indices for the lowest nonzero entries respectively as in~$[1~4]$ and in~$[2~3]$. The correctness of this homotopy (proven in~\cite{hss98} and~\cite{hv99}) justifies the formal root count using the localization poset. This combinatorial root count proceeds in two stages. First we build up the poset, from the bottom up, diminishing the entries in the brackets under the restriction that the same entry never occurs twice or more. Secondly, we descend from the top of the poset, collecting and adding up the counts at the nodes in the poset. More examples and variations are in~\cite{hv99}. \medskip To solve the general intersection problem of Theorem~\ref{theoprob2}, the special $(m+1-k_i)$-planes lie in the intersection of special $m$-planes. In the construction of the poset one has to follow additional rules as to ensure a solution that meets the intersection of special $m$-planes. We refer to~\cite{hv99} for details. \medskip The third enumerative problem we can solve is formalized as follows. \begin{theorem} \label{theoprob3} The number of all maps of degree $q$ that produce $r$-planes in $\cc^{m+r}$ meeting $mr + q(m+r)$ general $m$-planes at specified interpolation points is a finite constant. \end{theorem} In~\cite{rrw96,rrw98} and~\cite{wrr94} explicit formulas are given for this finite constant along with other combinatorial identities. Following a hint of Frank Sottile (see also~\cite{sot99a}) and reverse engineering on the root counts in~\cite{rrw96}, Pieri homotopies were developed in~\cite{hv99} whose correctness yields a proof for Theorem~\ref{theoprob3}. \medskip The analogue to Figure~\ref{figcelldeco} for maps of degree one into $G_{22}$ is displayed in Figure~\ref{figcurvcelldeco}. \begin{figure}[hbt] \begin{center} \begin{picture}(220,120)(20,-10) \thicklines \put(-65,85){\small ${\rm det}\left[ S_X \left| \begin{array}{cc} x^0_{11} & x^1_{12} s~~~ \\ x^0_{21} & ~~~x^0_{22} t \\ 0 & ~~~x^0_{32} t \\ 0 & ~~~x^0_{42} t \\ \end{array} \right. \right] = 0$} \put(140,85){\small ${\rm det}\left[ S_X \left| \begin{array}{cc} x^0_{11} & 0 \\ x^0_{21} & x^0_{22} \\ x^0_{31} & x^0_{32} \\ 0 & x^0_{42} \\ \end{array} \right. \right] = 0$} \put(110,50){\line(4,1){40}} \put(90,50){\line(-4,1){40}} \put(-10,15){\small ${\rm det}[L_n | X(s,t)] = {\rm det}\left[ L_n \left| \begin{array}{cc} x^0_{11} & x^1_{12} s~~~ \\ x^0_{21} & ~~~x^0_{22} t \\ x^0_{31} & ~~~x^0_{32} t \\ 0 & ~~~x^0_{42} t \\ \end{array} \right. \right] = 0$} \put(260,10){[3~5]} \put(227,30){[2~5]} \put(293,30){[3~4]} \put(257,18){\line(-2,1){10}} \put(285,18){\line(2,1){10}} \end{picture} \caption{Part of a cellular decomposition of the Grassmannian of maps of degree~1 that produce 2-planes in projective 3-space. The bracket notation at the right corresponds to a matrix representation of the coefficients of the map~$X(s,t)$. } \label{figcurvcelldeco} \end{center} \end{figure} To solve the problem in Theorem~\ref{theoprob3} we need a special position for the interpolation points. By moving those to infinity, the dominant monomials in the maps allow to re-use the same special $m$-planes, whose entries should be considered modulo~$m+r$. The homotopy to satisfy the $n$-th intersection condition is: \begin{equation} \label{eqpieriqhom} H(X(s,t),s,t) = \left\{ \begin{array}{rl} \det(L_i | X(s_i,t_i)) = 0 & i=1,2,\ldots,n-1 \\ \det((1-t) S_X + t L_n | X(s,t) ) = 0 & \\ (s-1)(1-t) + (s-s_n)t = 0 & t \in [0,1] \end{array} \right. \end{equation} Note that the continuation parameter~$t$ moves the interpolation point from infinity, at $(s,t) = (1,0)$, to the specific value $(s,t) = (s_n,1)$. \medskip See~\cite{sot99a} for information on the selection of the input planes so that all maps are real. \medskip As an example of another problem in enumerative geometry we mention the 27 lines on a cubic surface in 3-space. According to~\cite{mum76}, this is one of the gems hidden in the rag-bag of projective geometry. In~\cite{seg42}, the 27 lines are determined by breaking up the cubic surface into three planes in a continuous way such that each intermediate position is nonsingular. It is shown that this continuous variation is also valid in the real field. \section{Numerical Software for Solving Polynomial Systems} In computer algebra one wants to compute exactly as long as possible and to defer the approximate calculations to the very last end. Exactly the opposite way is taken in homotopy methods: here we use floating-point arithmetic and only increase the precision when needed. \medskip Next we mention programs with special features for polynomial systems. See~\cite[Chapter VIII]{ag97} for a list of available software for path following. HOMPACK~\cite{msw89,wbm87} is a general continuation package with a polynomial driver. It has been parallelized~\cite{acw89,hw89}, extended with an end game~\cite{sws96}, and upgraded~\cite{wsmmw97} to Fortran~90. POLSYS\_PLP~\cite{wsw98} provides linear-product root counts to be used in conjunction with HOMPACK90. The Fortran code for CONSOL is contained in~\cite[Appendix 6]{mor87}. The C-program pss~\cite{mal96} applies homotopy continuation with verification by $\alpha$-theory. Pelican~\cite{hub95,hub96} implements in~C the polyhedral methods of~\cite{hs95}. Efficient Fortran software for polyhedral continuation with facilities to compute all affine roots is used in~\cite{glw98}. The computation of mixed volumes with the C program mvlp~\cite{emi94,ec95} is a crucial step for sparse resultants~\cite{wem98}. A distributed version has been created in~\cite{gio96}. \medskip PHC is written in Ada and originated during the doctoral research of the author~\cite{ver96}. Executable versions were first released at the PoSSo open workshop on software~\cite{ver95}. The public release of the sources is described in~\cite{ver97}. The package is organized as a tool box, organized along four stages of the solver. Figure~\ref{figstages} presents the flow of the solver. The package is menu-driven and file-oriented. A general-purpose black-box solver is available. {\small \begin{figure}[hbt] \begin{center} \begin{picture}(360,145)(10,0) \put(20,120){\framebox(130,20)[c]{1. Preconditioning}} \put(50,100){$\diamond$ Coefficient Scaling} \put(50,85){$\diamond$ Reduction of degrees} \put(205,120){\framebox(130,20)[c]{4. Validation}} \put(235,100){$\diamond$ Refining of the roots} \put(235,85){$\diamond$ Analysis of condition $\#$s} \put(20,50){\framebox(130,20)[c]{2. Root Counting}} \put(30,35){$\diamond$ B\'ezout : degrees} \put(30,20){$\diamond$ Bernshtein : polytopes} \put(30,5){$\diamond$ Schubert : SAGBI/Pieri} \put(205,50){\framebox(140,20)[c]{3. Homotopy Continuation}} \put(215,30){$\diamond$ Fix continuation parameters} \put(215,15){$\diamond$ Choose Predictor-Corrector} \put(160,57){\line(1,0){25}} \put(160,60){\line(1,0){25}} \put(185,64){\line(2,-1){11}} \put(185,53){\line(2,1){11}} \put(34,113){\line(0,-1){25}} \put(38,113){\line(0,-1){25}} \put(31,91){\line(1,-2){5}} \put(41,91){\line(-1,-2){5}} \put(219,107){\line(0,-1){25}} \put(223,107){\line(0,-1){25}} \put(216,102){\line(1,2){5}} \put(226,102){\line(-1,2){5}} \end{picture} \caption{The four stages in the flow of the PHC solver.} \label{figstages} \end{center} \end{figure} } The new second release of PHC uses Ada~95 concepts in the construction of the mathematical library. It is developed with the freely available gnu-ada compiler (currently at version 3.11p) on various platforms. To run the software no compilation is needed, as binaries are available for Unix Workstations: running SUN Solaris and SGI Irix, and Pentium PCs: running Linux and Solaris. The portability of PHC is ensured by the gnu-ada compiler. \medskip Another main feature of the second release are the homotopy methods for the Schubert calculus. Implementing those homotopies was a matter of plugging in the equations and calling the path trackers. The third release of the package should offer a more comprehensive environment to construct homotopies, providing an easier access to the two main computational engines: mixed-volume computation and polynomial continuation. \section{The Database of Applications} The polynomial systems in scientific and engineering models are a continuing source of open problems. Systems that come from academic questions are often conjectures providing computational evidence in a developing theory. In various engineering disciplines polynomial systems represent a modeling problem, e.g.: a mechanical device. The origin of a polynomial system matters when the original problem formulation does not admit well-conditioned solutions. As a general method to deal with badly scaled systems to compute equilibria of chemical reaction systems, coefficient and equation scaling was developed in~\cite{mm87}, see also~\cite[Chapter 5]{mor87} and~\cite{wbm87}. \medskip The collection of test systems is organized as a database and available via the author's web pages, A good test example reveals properties of the solution method and has a meaningful application. Besides the algebraic formulation it contains the fields: title (meaningful description), references (problem source), root counts (B\'ezout bounds and mixed volume), and solution list. \medskip \noindent Instead of producing a huge list with an overview, we pick some important case studies. \begin{description} \item[{\bf katsura-n}] ({\em magnetism problem~{\rm \cite{kat94}}}) The number of solutions equals the total degree $D = 2^n$, so the homotopy based on~$D$ is optimal to solve this problem. Because the constant term is missing in all except one equation, the system is an interesting test problem for affine polyhedral methods. \smallskip \item[{\bf camera1s}] ({\em computer vision~{\rm \cite{fm90}}}) The system models the displacement of a camera between two positions in a static environment~\cite{emi94}. The multi-homogeneous homotopy is optimal for this problem, requiring 20 solution paths to trace instead of~$D = 64$. \smallskip \item[{\bf game$n$two}] ({\em totally mixed Nash equilibria for $n$ players with two strategies~{\rm \cite{mm97,mcl97}}}) This is another instance where multi-homogeneous homotopies are optimal. The number of solutions grows like $n! e^{-1}$ as $n \rightarrow \infty$. The largest system that is currently completely solvable is for $n = 8$ requiring 14,833 paths to trace. Situations exist for which all solutions are meaningful. \smallskip \item[{\bf cassou}] ({\em real algebraic geometry}) This system illustrates the success story of polyhedral homotopies: the total degree equals~1,344, best known B\'ezout bound is 312 (see~\cite{lww96}), whereas the mixed volume gives~24. Still eight paths are diverging to infinity and polyhedral end games~\cite{hv98} are needed to separate those diverging paths from the from the other finite ill-conditioned roots. \smallskip \item[{\bf cyclic-n}] ({\em Fourier transforms~{\rm \cite{bjo89,bf91}}}) For $n=7$, polyhedral homotopies are optimal, with all 924 paths leading to finite solutions. For $n \geq 8$, the mixed volume overestimates the number of roots and there are components of solutions. In~\cite{sv99} the degrees of the components were computed for $n=8,9$. There are 34940 cyclic 10-roots, generated by 1747 solutions. \smallskip \item[{\bf pole28sys}] ({\em pole placement problem~{\rm \cite{byr89}}}) This system illustrates the efficiency of SAGBI homotopies for verifying a conjecture in real algebraic geometry~\cite{sot98}. With the input planes chosen to osculate a rational normal curve, an instance with all 1,430 solutions real and isolated was solved in~\cite{ver98}. The problem is relevant to control theory~\cite{rw99}. \smallskip \item[{\bf stewgou40}] ({\em mechanism design~{\rm \cite{die98}}}) Whether the Stewart-Gough parallel platform in robotics could have all its 40 solutions real was a notorious open problem, until recently, as it was solved by numerical continuation methods~\cite{die98}. The problem formulation in~\cite{die98} is highly deficient: the mixed volume equals 1,536 whereas only 40 solution paths will converge. \end{description} We emphasize that we have optimal homotopies for three classes of polynomial systems, but not for all possible structures. Although one can solve a modelling problem by a black-box polynomial-system solver, knowing the origin of the problem leads in most cases to more favorable algebraic formulations that help the resolution of a polynomial system. To produce really meaningful solutions one often has to be close to the source of the problems and be able to interact with the people who formulate the polynomial systems. \medskip In closing this section we list some notable usages of PHC. Charles Wampler~\cite{wam96} used a preliminary version of PHC to count the roots of various systems in mechanical design. Root counts for linear subspace intersections in the Schubert calculus were computed by Frank Sottile, see~\cite{sot98} for various tables. A third example comes from computer graphics. To show that the 12 lines tangent to four given spheres can all be real, Thorsten Theobald used PHC, choosing appropriate parameters in the algebraic formulation set up by Cassiano Durand. \section{Closing Remarks and Open Problems} The three classes presented in this paper are by no means exhaustive, but give an idea of what can be done with homotopies to solve polynomial systems. The root counts constitute the theoretical backbone for general-purpose black-box solving. Yet, the homotopy methods are flexible enough to exploit a particular geometrical situation, with guaranteed optimal complexity when applied to generic instances. \medskip From algebraic geometry formal procedures based on intersection theory count the number of solutions to classes of polynomial systems. Examples are the theorems of B\'ezout, Bernshte\v{\i}n and Schubert. For these situations we construct a start system and have a homotopy to deform the solutions to this start system to the solutions to any specific problem. There are many other cases for which one knows how to count but not how to deform and solve efficiently. Research in homotopy methods is aimed at turning the formal root counts into effective numerical methods. As open problem we can ask for a meta-homotopy method to connect formal root counting methods to solving generic systems and deformation procedures. \medskip In most applications, only the real solutions are important. Once we know an optimal homotopy to solve the problem in the complex case, we would like to know whether all solutions can be real and how the real solutions are distributed. The reality question appears for instance in the theory of totally mixed Nash equilibria and in the pole placement problem. Finding well-conditioned instances of fully real problems can be done by homotopy methods. The finding of 40 real solutions to the Stewart-Gough platform~\cite{die98} is perhaps the most striking example. The question is to find an efficient procedure to deform from the complex case to the fully real case. \bigskip \noindent {\bf Acknowledgments.} The interest in homotopy methods by the FRISCO project has stimulated the author's research. The author is deeply indebted to all his co-authors. The interactions with Birk Huber and Frank Sottile at MSRI were influential in this current treatment of homotopies. \newpage {\small %\bibliography{art} \begin{thebibliography}{100} \bibitem{abh90} S.S. Abhyankar. \newblock {\em Algebraic Geometry for Scientists and Engineers}, volume~35 of {\em Mathematical Surveys and Monographs}. \newblock American Mathematical Society, Providence, Rhode Island, 1990. \bibitem{all84} E.L. Allgower. \newblock Bifurcation arising in the calculation of critical points via homotopy methods. \newblock In T.~Kupper, H.D. Mittleman, and N.~Weber, editors, {\em Numerical Methods for Bifurcation Problems}, pages 15--28. Birkh\"auser, Boston, 1984. \bibitem{ag90} E.L. Allgower and K.~Georg. \newblock {\em Numerical {C}ontinuation {M}ethods, an {I}ntroduction}, volume~13 of {\em Springer Ser. in Comput. Math.} \newblock Springer--Verlag, Berlin Heidelberg New York, 1990. \bibitem{ag93} E.L. Allgower and K.~Georg. \newblock Continuation and path following. \newblock {\em Acta Numerica}, pages 1--64, 1993. \bibitem{ag97} E.L. Allgower and K.~Georg. \newblock Numerical {P}ath {F}ollowing. \newblock In P.G. Ciarlet and J.L. Lions, editors, {\em Techniques of Scientific Computing (Part 2)}, volume~5 of {\em Handbook of Numerical Analysis}, pages 3--203. North-Holland, 1997. \bibitem{acw89} D.C.S. Allison, A.~Chakraborty, and L.T. Watson. \newblock Granularity issues for solving polynomial systems via globally convergent algorithms on a hypercube. \newblock {\em J. of Supercomputing}, 3:5--20, 1989. \bibitem{ber75} D.N. Bernshte{\v{\i}}n. \newblock The number of roots of a system of equations. \newblock {\em Functional Anal. Appl.}, 9(3):183--185, 1975. \newblock Translated from {\em Funktsional. Anal. i Prilozhen.}, 9(3):1--4,1975. \bibitem{bjo89} G.~Bj\"{o}rck. \newblock Functions of modulus one on ${Z}_n$ whose {F}ourier transforms have constant modulus, and "cyclic n-roots". \newblock In J.S. Byrnes and J.F. Byrnes, editors, {\em Recent Advances in {F}ourier Analysis and its Applications}, volume 315 of {\em NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci.}, pages 131--140. Kluwer, 1989. \bibitem{bf91} G.~Bj\"{o}rck and R.~Fr\"{o}berg. \newblock A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic n-roots. \newblock {\em J. Symbolic Computation}, 12(3):329--336, 1991. \bibitem{bcss97} L.~Blum, F.~Cucker, M.~Shub, and S.~Smale. \newblock {\em Complexity and Real Computation}. \newblock Springer--Verlag, New York, 1997. \bibitem{bm84} P.~Brunovsk\'{y} and P.~Merav\'{y}. \newblock Solving systems of polynomial equations by bounded and real homotopy. \newblock {\em Numer. Math.}, 43(3):397--418, 1984. \bibitem{byr89} C.I. Byrnes. \newblock Pole assignment by output feedback. \newblock In H.~Nijmacher and J.M. Schumacher, editors, {\em Three Decades of Mathematical Systems Theory}, volume 135 of {\em Lecture Notes in Control and Inform. Sci.}, pages 13--78. Springer--Verlag, Berlin, 1989. \bibitem{cr91} J.~Canny and J.M. Rojas. \newblock An optimal condition for determining the exact number of roots of a polynomial system. \newblock In {\em Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation}, pages 96--101. ACM, 1991. \bibitem{cmy79} S.N. Chow, J.~Mallet-Paret, and J.A. Yorke. \newblock Homotopy method for locating all zeros of a system of polynomials. \newblock In H.O. Peitgen and H.O. Walther, editors, {\em Functional differential equations and approximation of fixed points}, volume 730 of {\em Lecture Notes in Mathematics}, pages 77--88, Berlin Heidelberg, 1979. Springer--Verlag. \bibitem{cls97} D.~Cox, J.~Little, and D.~O'Shea. \newblock {\em Ideals, {V}arieties and {A}lgorithms. {A}n {I}ntroduction to {C}omputational {A}lgebraic {G}eometry and {C}ommutative {A}lgebra.} \newblock Undergraduate Texts in Mathematics. Springer--Verlag, New York, 2nd edition, 1997. \bibitem{cls98} D.~Cox, J.~Little, and D.~O'Shea. \newblock {\em Using Algebraic Geometry}, volume 185 of {\em Graduate Texts in Mathematics}. \newblock Springer--Verlag, New York, 1998. \bibitem{ds97} J.P. Dedieu and M.~Shub. \newblock Multihomogeneous {N}ewton methods. \newblock To appear in {\em Math. Comp.} \bibitem{die98} P.~Dietmaier. \newblock The {S}tewart-{G}ough platform of general geometry can have 40 real postures. \newblock In J.~Lenarcic and M.L. Husty, editors, {\em Advances in Robot Kinematics: Analysis and Control}, pages 1--10. Kluwer Academic Publishers, Dordrecht, 1998. \bibitem{dre77} F.J. Drexler. \newblock Eine {M}ethode zur {B}erechnung s\"{a}mtlicher {L}\"{o}sungen von {P}olynomgleichungssystemen. \newblock {\em Numer. Math.}, 29(1):45--58, 1977. \bibitem{df88} M.E. Dyer and A.M. Frieze. \newblock On the complexity of computing the volume of a polyhedron. \newblock {\em SIAM J. Comput.}, 17(5):967--974, 1988. \bibitem{dgh98} M.~Dyer, P.~Gritzmann, and A.~Hufnagel. \newblock On the complexity of computing mixed volumes. \newblock {\em SIAM J. Comput.}, 27(2):356--400, 1998. \bibitem{eis95} D.~Eisenbud. \newblock {\em Commutative Algebra with a View Toward Algebraic Geometry}, volume 150 of {\em Graduate Texts in Mathematics}. \newblock Springer--Verlag, New York, 1995. \bibitem{emi94} I.Z. Emiris. \newblock {\em Sparse Elimination and Applications in Kinematics}. \newblock PhD thesis, Computer Science Division, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, 1994. \bibitem{ec95} I.Z. Emiris and J.F. Canny. \newblock Efficient incremental algorithms for the sparse resultant and the mixed volume. \newblock {\em J. Symbolic Computation}, 20(2):117--149, 1995. \newblock Software available at {\tt http://www.inria.fr/saga/emiris}. \bibitem{emi96} I.Z. Emiris. \newblock On the complexity of sparse elimination. \newblock {\em J. Complexity}, 12(2):134--166, 1996. \bibitem{ev99} I.Z. Emiris and J.~Verschelde. \newblock How to count efficiently all affine roots of a polynomial system. \newblock {\em Discrete Applied Mathematics}, 93(1):21--32, 1999. \bibitem{fal90} P.~Falb. \newblock {\em Methods of Algebraic Geometry in Control Theory: Part I, Scalar Linear Systems and Affine Algebraic Geometry}, volume~4 of {\em Systems \& Control: Foundations \& Applications}. \newblock Birkh\"auser, Boston, 1990. \bibitem{fm90} O.D. Faugeras and S.~Maybank. \newblock Motion from point matches: multiplicity of solutions. \newblock {\em Intern. J. Comp. Vision}, 4:225--246, 1990. \bibitem{glw98} T.~Gao, T.Y. Li, and X.~Wang. \newblock Finding isolated zeros of polynomial systems in ${C}^n$ with stable mixed volumes. \newblock To appear in {\em J. of Symbolic Computation}. \bibitem{glvw98} T.~Gao, T.Y. Li, J.~Verschelde, and M.~Wu. \newblock Balancing the lifting values to improve the numerical stability of polyhedral homotopy continuation methods. \newblock To appear in {\em Applied Math. Comput.} \bibitem{gz79} C.B. Garcia and W.I. Zangwill. \newblock Finding all solutions to polynomial systems and other systems of equations. \newblock {\em Math. Programming}, 16(2):159--176, 1979. \bibitem{gl80} C.B. Garcia and T.Y. Li. \newblock On the number of solutions to polynomial systems of equations. \newblock {\em SIAM J. Numer. Anal.}, 17(4):540--546, 1980. \bibitem{gkz94} I.M. {Gel'fand}, M.M. Kapranov, and A.V. Zelevinsky. \newblock {\em {D}iscriminants, {R}esultants and {M}ultidimensional {D}eterminants}. \newblock Birkh\"auser, Boston, 1994. \bibitem{gio96} T.~Giordano. \newblock Impl\'{e}mention distribu\'{e}e du calcul du volume mixte. \newblock Master's thesis, University of Nice, Sophia-Antipolis, 1996. \bibitem{gr97} J.E. Goodman and J.~O'Rourke (editors). \newblock {\em Handbook of Discrete and Computational Geometry}. \newblock CRC Press, New York, 1997. \bibitem{hw89} S.~Harimoto and L.T. Watson. \newblock The granularity of homotopy algorithms for polynomial systems of equations. \newblock In G.~Rodrigue, editor, {\em Parallel processing for scientific computing}, pages 115--120. SIAM, 1989. \bibitem{har95} J.~Harris. \newblock {\em Algebraic Geometry, A first Course}, volume 133 of {\em Graduate Texts in Mathematics}. \newblock Springer--Verlag, New York, 1992. \newblock Corrected third printing, 1995. \bibitem{hk90} M.E. Henderson and H.B. Keller. \newblock Complex bifurcation from real paths. \newblock {\em SIAM J. Appl. Math.}, 50:460--482, 1990. \bibitem{hub95} B.~Huber. \newblock Pelican manual. \newblock Available at {http://www.msri.org/people/members/birk}. \bibitem{hs95} B.~Huber and B.~Sturmfels. \newblock A polyhedral method for solving sparse polynomial systems. \newblock {\em Math. Comp.}, 64(212):1541--1555, 1995. \bibitem{hub96} B.T. Huber. \newblock {\em Solving Sparse Polynomial Systems}. \newblock PhD thesis, Cornell University, 1996. \newblock Available at {http://www.msri.org/people/members/birk}. \bibitem{hs97} B.~Huber and B.~Sturmfels. \newblock Bernstein's theorem in affine space. \newblock {\em Discrete Comput. Geom.}, 17(2):137--141, 1997. \bibitem{hv98} B.~Huber and J.~Verschelde. \newblock Polyhedral end games for polynomial continuation. \newblock {\em Numerical Algorithms}, 18(1):91--108, 1998. \bibitem{hss98} B.~Huber, F.~Sottile, and B.~Sturmfels. \newblock Numerical {S}chubert calculus. \newblock {\em J. of Symbolic Computation}, 26(6):767--788, 1998. \bibitem{hrs99} B~Huber, J.~Rambau, and F.~Santos. \newblock The {C}ayley trick, lifting subdivisions and the {B}ohne-{D}ress theorem on zonotopal tilings. \newblock Submitted to the {\em Journal of the European Mathematical Society}., 1999. \bibitem{hv99} B.~Huber and J.~Verschelde. \newblock Pieri homotopies for problems in enumerative geometry applied to pole placement in linear systems control. \newblock {MSRI} {P}reprint \#1998-064, 1999. \bibitem{kat94} S.~Katsura. \newblock Users posing problems to posso. \newblock PoSSo Newsletter, no. 2, July 1994, edited by L. Gonzalez-Vega and T. Recio. Available at http://posso.dm.unipi.it/. \bibitem{kem93} G.R. Kempf. \newblock {\em Algebraic Varieties}, volume 172 of {\em London Mathematical Society Lecture Note Series}. \newblock Cambridge University Press, 1993. \bibitem{kho78} A.G. Khovanski{\v{\i}}. \newblock Newton polyhedra and the genus of complete intersections. \newblock {\em Functional Anal. Appl.}, 12(1):38--46, 1978. \newblock Translated from {\em Funktsional. Anal. i Prilozhen.}, 12(1),51--61,1978. \bibitem{kss98} H.~Kobayashi, H.~Suzuki, and Y.~Sakai. \newblock Numerical calculation of the multiplicity of a solution to algebraic equations. \newblock {\em Math. Comp.}, 67(221):257--270, 1998. \bibitem{kus76} A.G. Kushnirenko. \newblock Newton {P}olytopes and the {B}\'{e}zout {T}heorem. \newblock {\em Functional Anal. Appl.}, 10(3):233--235, 1976. \newblock Translated from {\em Funktsional. Anal. i Prilozhen.}, 10(3),82--83,1976. \bibitem{li83} T.Y. Li. \newblock On {C}how, {M}allet-{P}aret and {Y}orke homotopy for solving systems of polynomials. \newblock {\em Bulletin of the Institute of Mathematics. Acad. Sin.}, 11:433--437, 1983. \bibitem{li87} T.Y. Li. \newblock Solving polynomial systems. \newblock {\em The Mathematical Intelligencer}, 9(3):33--39, 1987. \bibitem{ls87} T.Y. Li and T.~Sauer. \newblock Regularity results for solving systems of polynomials by homotopy method. \newblock {\em Numer. Math.}, 50(3):283--289, 1987. \bibitem{lsy87b} T.Y. Li, T.~Sauer, and J.A. Yorke. \newblock Numerical solution of a class of deficient polynomial systems. \newblock {\em SIAM J. Numer. Anal.}, 24(2):435--451, 1987. \bibitem{lsy87a} T.Y. Li, T.~Sauer, and J.A. Yorke. \newblock The random product homotopy and deficient polynomial systems. \newblock {\em Numer. Math.}, 51(5):481--500, 1987. \bibitem{lsy89} T.Y. Li, T.~Sauer, and J.A. Yorke. \newblock The cheater's homotopy: an efficient procedure for solving systems of polynomial equations. \newblock {\em SIAM J. Numer. Anal.}, 26(5):1241--1251, 1989. \bibitem{lw91} T.Y. Li and X.~Wang. \newblock Solving deficient polynomial systems with homotopies which keep the subschemes at infinity invariant. \newblock {\em Math. Comp.}, 56(194):693--710, 1991. \bibitem{lw92} T.Y. Li and X.~Wang. \newblock Nonlinear homotopies for solving deficient polynomial systems with parameters. \newblock {\em SIAM J. Numer. Anal.}, 29(4):1104--1118, 1992. \bibitem{lw93} T.Y. Li and X.~Wang. \newblock Solving real polynomial systems with real homotopies. \newblock {\em Math. Comp.}, 60:669--680, 1993. \bibitem{lw94} T.Y. Li and X.~Wang. \newblock Higher order turning points. \newblock {\em Appl. Math. Comput.}, 64:155--166, 1994. \bibitem{lw96} T.Y. Li and X.~Wang. \newblock The {BKK} root count in {$C^n$}. \newblock {\em Math. Comp.}, 65(216):1477--1484, 1996. \bibitem{lww96} T.Y. Li, T.~Wang, and X.~Wang. \newblock Random product homotopy with minimal {BKK} bound. \newblock In J.~Renegar, M.~Shub, and S.~Smale, editors, {\em The Mathematics of Numerical Analysis}, volume~32 of {\em Lectures in Applied Mathematics}, pages 503--512, 1996. \newblock Proceedings of the AMS-SIAM Summer Seminar in Applied Mathematics, Park City, Utah, July 17-August 11, 1995, Park City, Utah. \bibitem{li97} T.Y. Li. \newblock Numerical solution of multivariate polynomial systems by homotopy continuation methods. \newblock {\em Acta Numerica}, 6:399--436, 1997. \bibitem{lw98} T.Y. Li and X.~Wang. \newblock Counterexamples to the connectivity conjecture of the mixed cells. \newblock {\em Discrete Comput. Geom.}, 20(4):515--521, 1998. \bibitem{mal96} G.~Malajovich. \newblock pss 2 -- Polynomial System Solver. \newblock Available at {http://www.labma.ufrj.br:80/{\~{}}gregorio}. \bibitem{mm97} R.D. McKelvey and A.~McLennan. \newblock The maximal number of regular totally mixed {N}ash equilibria. \newblock {\em Journal of Economic Theory}, 72:411--425, 1997. \bibitem{mcl97} A.~McLennan. \newblock The maximal generic number of pure {N}ash equilibria. \newblock {\em Journal of Economic Theory}, 72:408--410, 1997. \bibitem{mm87} K.~Meintjes and A.P. Morgan. \newblock A methodology for solving chemical equilibrium systems. \newblock {\em Appl. Math. Comput.}, 22(4):333--361, 1987. \bibitem{mor83} A.P. Morgan. \newblock A method for computing all solutions to systems of polynomial equations. \newblock {\em ACM Trans. Math. Softw.}, 9(1):1--17, 1983. \bibitem{mor87} A.~Morgan. \newblock {\em Solving polynomial systems using continuation for engineering and scientific problems}. \newblock Prentice-Hall, Englewood Cliffs, N.J., 1987. \bibitem{ms87a} A.~Morgan and A.~Sommese. \newblock A homotopy for solving general polynomial systems that respects m-homogeneous structures. \newblock {\em Appl. Math. Comput.}, 24(2):101--113, 1987. \bibitem{ms87b} A.~Morgan and A.~Sommese. \newblock Computing all solutions to polynomial systems using homotopy continuation. \newblock {\em Appl. Math. Comput.}, 24(2):115--138, 1987. \newblock Errata: {\em Appl. Math. Comput.} 51 (1992), p. 209. \bibitem{msw89} A.P. Morgan, A.J. Sommese, and L.T. Watson. \newblock Finding all isolated solutions to polynomial systems using {HOMPACK}. \newblock {\em ACM Trans. Math. Softw.}, 15(2):93--122, 1989. \bibitem{ms89} A.P. Morgan and A.J. Sommese. \newblock Coefficient-parameter polynomial continuation. \newblock {\em Appl. Math. Comput.}, 29(2):123--160, 1989. \newblock Errata: {\em Appl. Math. Comput.} 51:207(1992). \bibitem{ms90} A.P. Morgan and A.J. Sommese. \newblock Generically nonsingular polynomial continuation. \newblock In E.L. Allgower and K.~Georg, editors, {\em Computational Solution of Nonlinear Systems of Equations}, pages 467--493, Providence, R.I., 1990. AMS. \bibitem{msw91} A.P. Morgan, A.J. Sommese, and C.W. Wampler. \newblock Computing singular solutions to nonlinear analytic systems. \newblock {\em Numer. Math.}, 58(7):669--684, 1991. \bibitem{msw92a} A.P. Morgan, A.J. Sommese, and C.W. Wampler. \newblock Computing singular solutions to polynomial systems. \newblock {\em Adv. Appl. Math.}, 13(3):305--327, 1992. \bibitem{msw92b} A.P. Morgan, A.J. Sommese, and C.W. Wampler. \newblock A power series method for computing singular solutions to nonlinear analytic systems. \newblock {\em Numer. Math.}, 63:391--409, 1992. \bibitem{msw95} A.P. Morgan, A.J. Sommese, and C.W. Wampler. \newblock A product-decomposition theorem for bounding {B}\'ezout numbers. \newblock {\em SIAM J. Numer. Anal.}, 32(4):1308--1325, 1995. \bibitem{mum76} D.~Mumford. \newblock {\em Algebraic {G}eometry I; {C}omplex {P}rojective {V}arieties}, volume 221 of {\em {G}rundlehren der mathematischen {W}issenschaften}. \newblock Springer--Verlag, Berlin Heidelberg New York, 1976. \bibitem{pie1891} M.~Pieri. \newblock Formule di coincidenza per le serie algebriche {$\infty^n$} di coppie di punti dello spazio a $n$ dimensioni. \newblock {\em Rend. Circ. Mat. Palermo}, 5:252--268, 1891. \bibitem{rrw96} M.S. Ravi, J.~Rosenthal, and X.~Wang. \newblock Dynamic pole placement assignment and {S}chubert calculus. \newblock {\em SIAM J. Control and Optimization}, 34(3):813--832, 1996. \bibitem{rrw98} M.S. Ravi, J.~Rosenthal, and X.~Wang. \newblock Degree of the generalized {P}l{\"{u}}cker embedding of a quot scheme and quatum cohomology. \newblock {\em Math. Ann.}, 311:11--26, 1998. \bibitem{roj94} J.M. Rojas. \newblock A convex geometric approach to counting the roots of a polynomial system. \newblock {\em Theoret. Comput. Sci.}, 133(1):105--140, 1994. \newblock Extensions and corrections available at http://www.cityu.edu.hk/ma/staff/rojas/. \bibitem{rw96} J.M. Rojas and X.~Wang. \newblock Counting affine roots of polynomial systems via pointed {N}ewton polytopes. \newblock {\em J. Complexity}, 12:116--133, 1996. \bibitem{roj99} J.M. Rojas. \newblock Toric intersection theory for affine root counting. \newblock {\em Journal of Pure and Applied Algebra}, 136(1):67--100, 1999. \bibitem{ros94} J.~Rosenthal. \newblock On dynamic feedback compensation and compactifications of systems. \newblock {\em SIAM J. Control and Optimization}, 32(1):279--296, 1994. \bibitem{rs98} J.~Rosenthal and F.~Sottile. \newblock Some remarks on real and complex output feedback. \newblock {\em Systems and Control Lett.}, 33(2):73--80, 1998. \newblock See {\tt http://www.nd.edu/{\~{}}rosen/pole} for a description of computational aspects of the paper. \bibitem{rw99} J.~Rosenthal and J.C. Willems. \newblock Open problems in the area of pole placement. \newblock In V.D. Blondel, E.D. Sontag, M.~Vidyasagar, and J.C. Willems, editors, {\em Open Problems in Mathematical Systems and Control Theory}, Communication and Control Engineering Series. Springer--Verlag, London, 1999. \bibitem{sch1891} H.~Schubert. \newblock Beziehungen zwischen den linearen {R}{\"{a}}umen auferlegbaren charakteristischen {B}edingungen. \newblock {\em Math. Ann.}, 38:588--602, 1891. \bibitem{seg42} B.~Segre. \newblock {\em The Non-Singular Cubic Surfaces. A New Method of Investigation with Special Reference to Questions of Reality}. \newblock Oxford University Press, 1942. \bibitem{sw96} A.J. Sommese and C.W. Wampler. \newblock Numerical algebraic geometry. \newblock In J.~Renegar, M.~Shub, and S.~Smale, editors, {\em The Mathematics of Numerical Analysis}, volume~32 of {\em Lectures in Applied Mathematics}, pages 749--763, 1996. \newblock Proceedings of the AMS-SIAM Summer Seminar in Applied Mathematics, Park City, Utah, July 17-August 11, 1995, Park City, Utah. \bibitem{sv99} A.J. Sommese and J.~Verschelde. \newblock Numerical homotopies to compute generic points on positive dimensional algebraic sets. \newblock {MSRI} {P}reprint \#1999-038, 1999. \bibitem{sws96} M.~Sosonkina, L.T. Watson, and D.E. Stewart. \newblock Note on the end game in homotopy zero curve tracking. \newblock {\em ACM Trans. Math. Softw.}, 22(3):281--287, 1996. \bibitem{sot97a} F.~Sottile. \newblock Enumerative geometry for real varieties. \newblock In J.~Koll{\'{a}}r, R.~Lazarsfeld, and D.~R. Morrison, editors, {\em Algebraic Geometry - Santa Cruz 1995 (University of California, Santa Cruz, July 1995)}, volume 62, Part I of {\em Proceedings of Symposia in Pure Mathematics}, pages 435--447. AMS, 1997. \bibitem{sot97b} F.~Sottile. \newblock Pieri's formula via explicit rational equivalence. \newblock {\em Can. J. Math.}, 49(6):1281--1298, 1997. \bibitem{sot98} F.~Sottile. \newblock Real {S}chubert calculus: polynomial systems and a conjecture of {S}hapiro and {S}hapiro. \newblock {MSRI} {P}reprint \#1998-066, 1998. \newblock Accepted for publication in {\em Experimental Mathematics}. \bibitem{sot99b} F.~Sottile. \newblock The special {S}chubert calculus is real. \newblock {\em Electronic Research Announcements of the AMS}, 5:35--39, 1999. \newblock Available at {\tt http://www.ams.org/era}. \bibitem{sot99a} F.~Sottile. \newblock Real rational curves in {G}rassmannians. \newblock {MSRI} {P}reprint \#1999-025, 1999. \bibitem{stu93} B.~Sturmfels. \newblock {\em Algorithms in Invariant Theory}. \newblock Texts and Monographs in Symbolic Computation. Springer--Verlag, New York, 1993. \bibitem{stu94} B.~Sturmfels. \newblock On the {N}ewton polytope of the resultant. \newblock {\em Journal of Algebraic Combinatorics}, 3:207--236, 1994. \bibitem{stu96} B.~Sturmfels. \newblock {\em Gr{\"{o}}bner {B}ases and {C}onvex {P}olytopes}, volume~8 of {\em University Lecture Series}. \newblock AMS, Providence, R.I., 1996. \bibitem{stu98} B.~Sturmfels. \newblock Polynomial equations and convex polytopes. \newblock {\em Amer. Math. Monthly}, 105(10):907--922, 1998. \bibitem{vbh91} J.~Verschelde, M.~Beckers, and A.~Haegemans. \newblock A new start system for solving deficient polynomial systems using continuation. \newblock {\em Appl. Math. Comput.}, 44(3):225--239, 1991. \bibitem{vc93b} J.~Verschelde and R.~Cools. \newblock Symbolic homotopy construction. \newblock {\em Applicable Algebra in Engineering, Communication and Computing}, 4(3):169--183, 1993. \bibitem{vc94a} J.~Verschelde and R.~Cools. \newblock Symmetric homotopy construction. \newblock {\em J. Comput. Appl. Math.}, 50:575--592, 1994. \bibitem{vg95} J.~Verschelde and K.~Gatermann. \newblock Symmetric {N}ewton polytopes for solving sparse polynomial systems. \newblock {\em Adv. Appl. Math.}, 16(1):95--127, 1995. \bibitem{vh93a} J.~Verschelde and A.~Haegemans. \newblock The {{\em GBQ}}-{A}lgorithm for constructing start systems of homotopies for polynomial systems. \newblock {\em SIAM J. Numer. Anal.}, 30(2):583--594, 1993. \bibitem{vvc94} J.~Verschelde, P.~Verlinden, and R.~Cools. \newblock Homotopies exploiting {N}ewton polytopes for solving sparse polynomial systems. \newblock {\em SIAM J. Numer. Anal.}, 31(3):915--930, 1994. \bibitem{ver95} J.~Verschelde. \newblock {PHC} and {MVC}: two programs for solving polynomial systems by homotopy continuation. \newblock In J.C. Faug{\`{e}}re, J.~Marchand, and R.~Rioboo, editors, {\em Proceedings of the PoSSo Workshop on Software. Paris, March 1--4, 1995}, pages 165--175, 1995. \bibitem{vgc96} J.~Verschelde, K.~Gatermann, and R.~Cools. \newblock Mixed-volume computation by dynamic lifting applied to polynomial system solving. \newblock {\em Discrete Comput. Geom.}, 16(1):69--112, 1996. \bibitem{ver96} J.~Verschelde. \newblock {\em Homotopy Continuation Methods for Solving Polynomial Systems}. \newblock PhD thesis, K.U.Leuven, Dept. of Computer Science, 1996. \newblock Postscript version available from the author's web pages. \bibitem{ver98} J.~Verschelde. \newblock Numerical evidence for a conjecture in real algebraic geometry. \newblock {MSRI} {P}reprint \#1998-064, 1998. \newblock Accepted for publication in {\em Experimental Mathematics}. Paper and software available at the author's web-pages. \bibitem{ver97} J.~Verschelde. \newblock {PHC}pack: A general-purpose solver for polynomial systems by homotopy continuation. \newblock Accepted for publication in {\em ACM Trans. Math. Softw.}. Paper and software available at the author's web-pages., 1999. \bibitem{ver99} J.~Verschelde. \newblock Toric {N}ewton method for polynomial homotopies. \newblock {MSRI} {P}reprint \#1999-005, 1999. \newblock Revised for special issue of {\em J. Symbolic Computation}. \bibitem{wem98} A.~Wallack, I.Z. Emiris, and D.~Manocha. \newblock {MARS: A M}aple/{M}atlab/{C} resultant-based solver. \newblock In O.~Gloor, editor, {\em Proceedings of ISSAC-98}, pages 244--251, Rostock, Germany, 1998. ACM. \bibitem{wms90} C.W. Wampler, A.P. Morgan, and A.J. Sommese. \newblock Numerical continuation methods for solving polynomial systems arising in kinematics. \newblock {\em ASME J. of Mechanical Design}, 112(1):59--68, 1990. \bibitem{wms92a} C.W. Wampler, A.P. Morgan, and A.J. Sommese. \newblock Complete solution of the nine-point path synthesis problem for four-bar linkages. \newblock {\em ASME J. of Mechanical Design}, 114(1):153--159, 1992. \bibitem{wam92} C.W. Wampler. \newblock Bezout number calculations for multi-homogeneous polynomial systems. \newblock {\em Appl. Math. Comput.}, 51(2--3):143--157, 1992. \bibitem{wam96} C.W. Wampler. \newblock Isotropic coordinates, circularity and {B}ezout numbers: planar kinematics from a new perspective. \newblock Proceedings of the 1996 ASME Design Engineering Technical Conference. Irvine, CA, Aug 18--22, 1996. Available on CD-ROM. \bibitem{wrr94} X.~Wang, M.S. Ravi, and J.~Rosenthal. \newblock Algebraic and combinatorial aspects of the dynamic pole assignment problem. \newblock In U.~Helmke, R.~Mennicken, and J.~Saurer, editors, {\em Systems and Networks: Mathematical Theory and Applications}, volume~79 of {\em Mathematical Research}, pages 547--550. Akademie Verlag, Berlin, 1994. \newblock Proc. of the International Symposium MTNS 93 held in Regensburg Germany. Vol II: Invited and contributed papers. \bibitem{wat86} L.T. Watson. \newblock Numerical linear algebra aspects of globally convergent homotopy methods. \newblock {\em SIAM Rev.}, 28(4):529--545, 1986. \bibitem{wbm87} L.T. Watson, S.C. Billups, and A.P. Morgan. \newblock Algorithm 652: {HOMPACK}: a suite of codes for globally convergent homotopy algorithms. \newblock {\em ACM Trans. Math. Softw.}, 13(3):281--310, 1987. \bibitem{wat89} L.T. Watson. \newblock Globally convergent homotopy methods: a tutorial. \newblock {\em Appl. Math. Comput.}, 31(Spec. Issue):369--396, 1989. \bibitem{wsmmw97} L.T. Watson, M.~Sosonkina, R.C. Melville, A.P. Morgan, and H.F. Walker. \newblock {HOMPACK90}: A suite of {F}ortran 90 codes for globally convergent homotopy algorithms. \newblock {\em ACM Trans. Math. Softw.}, 23(4):514--549, 1997. \newblock Available at http://www.cs.vt.edu/{\~{}}ltw/. \bibitem{wei62} A.~Weil. \newblock {\em Foundations of Algebraic Geometry}, volume XXIX of {\em AMS Colloquium Publications}. \newblock AMS, Providence, Rhode Island, 1962. \newblock Revised and Enlarged Edition. \bibitem{wsw98} S.M. Wise, A.J. Sommese, and L.T. Watson. \newblock {POLSYS\_PLP}: A partitioned linear product homotopy code for solving polynomial systems of equations. \newblock Available at http://www.cs.vt.edu/{\~{}}ltw/, 1998. \bibitem{wri85} A.H. Wright. \newblock Finding all solutions to a system of polynomial equations. \newblock {\em Math. Comp.}, 44(169):125--133, 1985. \bibitem{zie95} G.M. Ziegler. \newblock {\em Lectures on {P}olytopes}, volume 152 of {\em Graduate Texts in Mathematics}. \newblock Springer--Verlag, New York, 1995. \bibitem{zul88} W.~Zulehner. \newblock A simple homotopy method for determining all isolated solutions to polynomial systems. \newblock {\em Math. Comp.}, 50(181):167--177, 1988. \end{thebibliography} } \end{document}