Next: 2.iii. Real Solutions to Sparse Polynomial Systems
Previous: 2.ii.b. Regular Triangulations

## 2.ii.c. Polyhedral homotopy algorithm

Crucial to the polyhedral homotopy algorithm of Huber and Sturmfels [HS] are polynomial systems derived from the original system and the regular subdivision Pw of P by a lifting function w. Given a polynomial f with Newton polytope P and a face F of the subdivision Pw, consider the sum of terms of f with exponent vector in the face F, restricting f to the face F. Doing this for each polynomial fi in our original system, we obtain the facial subsystem of (2.1) given by F.

Suppose we have a lifting function w : Lattice Points in P --> Q and a polynomial f with Newton polytope P

 f(x)   = ca xa ,

the sum over all integral lattice points a in P. We multiply the term with exponent a by tw(a) to obtain

 f(x;t)   := ca xa tw(a) ,

the sum over all integral lattice points a in P. Modifying all polynomials in the original sparse system in this way gives the lifted system, a family of sparse systems depending upon the parameter t.
 f1(x;t)   =   f2(x;t)   =   ...   =   fn(x;t)   =   0 , (2.4)

Solutions to this system are algebraic functions t |--> x(t) in the parameter t. In a neighborhood of 0 in the complex plane, each branch is expressed as a Puiseaux series

x(t)   =   (x1(t), x2(t), ..., xn(t))    with   xi(t)  =  tui yi  +  higher order terms in t ,

where the yi are non-zero constants and exponents ui are rational numbers. Substituting this expression into (2.4), we obtain

 0   = ca ya tua + w(a)   +   higher order terms in t .

(The sum here is once again over all integral lattice points a in P.) The exponent of t is the dot product of (u,1) with (a,w(a)). Thus the terms of lowest order in t correspond to points (a,w(a)) in the lifted polytope where the exponent vector (u,1) achieves its minimum--a face in the lower hull of the lifted polytope. Let F be the corresponding face of the regular subdivision Pw. Let b be any vertex of this face F. Removing the common factor tub + w(b) from these lowest order terms gives the restriction of f to the face F. Thus the coefficients yi of the leading terms of the Puiseaux expansion are solutions to the facial subsystem of the original system (2.1) given by the face F selected by the initial Puiseaux exponents.

Suppose the original system is general in the sense that each of its facial subsystems given by faces F of the regular subdivision has solutions only if VolF>0, that is, only if F is a facet of the subdivision. Consider substituting the Puiseaux series into the polynomial system (2.4) and then taking the limit as t approaches 0. The resulting polynomial system for the leading coefficients y of the Puiseaux series are solutions to the corresponding facial system. By previous assumption, this has no solutions unless F is a facet of the subdivision Pw. In that case, the inward pointing normal vector (u,1) to the corresponding facet of the lifted polytope gives the initial exponent u of the Puiseaux expansion.

The full Puiseaux series can be reconstructed from its initial terms (see [HS] for details) giving the 1-1 correspondence

 Solutions to facial subsystems of (2.1) given by facets of Pw <----> Branches of the algebraic function t |--> x(t) near t=0

This is the number of solutions to the lifted system (2.4) for general complex numbers t, so the number of solutions to the original sparse system (2.1) equals the number of solutions to all the facial subsystems given by facets of Pw.

Now suppose the regular subdivision Pw is a regular triangulation and each facial subsystem is general. Then the facets F of Pw are simplices with no interior vertices. Since general sparse systems whose Newton polytope is such a simplex have exactly n!Vol(F) solutions, the number of solutions to facial subsystems given by facets of Pw is exactly the sum of the normalized volumes of all facets of Pw, which is the normalized volume of P.

Next: 2.iii. Real Solutions to Sparse Polynomial Systems