Root Counts and Start Systems

Two different root-counting models and start systems are available:

1.

Based on the highest degrees  of the polynomials: random linear-product start systems;

2.

Based on the mixed volume of the Newton polytopes : random coefficient start systems.

The first class is well-suited for dense  polynomial systems, whereas Newton polytopes provide a good model to capture the sparsity  of a system.

The total degree 

is the product of the degrees  of the polynomials in the system. The i-th equation of the start system  is a univariate polynomial in the i-th unknown of the same degree as the i-th polynomial in the system that has to be solved. The total degree equals the number of solutions of the start system.

An m-homogeneous Bézout number  

is based on a partition  of the set of unknowns, with m the number of sets in the partition. The corresponding start system is a linear-product system:   the i-th equation is the product of linear equations with random coefficients in the unknowns of the set of the partition. The number of factors in the product of the i-th polynomial equals the product of the degrees of the i-th polynomial in the original system w.r.t. every set in the partition. Given a partition, the m-homogeneous Bézout number equals the number of solutions of the corresponding linear-product start system. Before the construction of the start system, an m-homogeneous Bézout number is first computed in a formal way as a generalized permanent of a degree matrix. Either all partitions of the set of unknowns can be evaluated, or the available heuristic procedure for generating a partition can be applied.

A partitioned linear-product Bézout number  

is based on a tuple of partitions of the set of unknowns. For every polynomial in the system, a different partition can model its structure. The corresponding start system is a linear-product system: the i-th equation is the product of linear equations with random coefficients in the unknowns of the set of the partition. The number of factors in the product for the i-th equation of the start system equals the product of the degrees of the i-th polynomial in the original system w.r.t. every set in the partition. Given a tuple of partitions, the partitioned linear-product Bézout number equals the number of solutions of the corresponding linear-product start system. Before the construction of the start system, a partitioned linear-product Bézout number is first computed in a formal way as a generalized permanent of a degree matrix. A heuristic procedure is available for generating a tuple of partitions.

A general linear-product Bézout number  

   is based on a supporting set structure. A set structure is a tuple of arrays of subsets of unknowns. The corresponding start system is a linear-product system: the i-th equation is the product of linear equations with random coefficient in the unknowns of the set of the i-th array. The number of factors in the product for the i-th equation of the start system equals the number of subsets in the i-th array of the set structure. A set structure is supporting for a polynomial system if every monomial in the system also occurs in the corresponding linear-product start system. Given a supporting set structure, the general linear-product Bézout number equals the number of solutions of the corresponding linear-product start system. Before the construction of the start system, a general linear-product Bézout number is first computed in a formal way as a generalized permanent of a degree matrix. A heuristic procedure is available for generating a supporting set structure.

A symmetric general linear-product Bézout number

is based on a symmetric supporting set structure  and allows to exploit permutation symmetries in the system. The corresponding linear-product start system has the same symmetric structure, so that in the homotopy, only the generating solution paths need to be traced.

The mixed volume 

of the tuple of Newton polytopes gives an upper bound for the number of complex isolated solutions with nonzero coefficients. This BKK bound (named to honor Bernshtein, Koushnirenko and Khovanskii) is exact when the coefficients are sufficiently chosen at random or when the polytopes are in generic position w.r.t. each other. By implicit lifting  , the mixed volume is computed by lifting up the origin of the first polytope and by computing those facets of the lower hull of the Minkowski sum that are spanned by edge-edge combinations. This procedure to compute the mixed volume uses recursion on the dimension. A random coefficient start system  has the same Newton polytopes as the target system, but all coefficients are randomly chosen complex numbers. To solve a random coefficient start system, homotopy continuation is invoked in a recursive way, similar to the computation of the mixed volume. By constructing a set structure for the first k equations and computing the mixed volumes of the remaining n-k equations obtained after elimination, a combined Bézout-BKK bound is computed.

Static lifting 

is a general procedure to construct regular mixed    subdivisions of a tuple of polytopes. For mixed-volume computation, only those cells that are spanned by a tuple of edges contribute to the mixed volume. These cells are the so-called mixed cells in the subdivision. The collection of mixed cells is computed efficiently by pruning in the tree of lifted edge-edge combinations. These mixed cells provide the start systems in the polyhedral homotopy   methods used to solve a random coefficient start system. Recursion is applied in case the lifting does not induce at once a fine mixed subdivision.

Dynamic lifting 

can be used to compute mixed volumes incrementally, i.e.: by adding the points repeatedly to the already constructed subdivision. This method works efficiently when all Newton polytopes are (almost) equal. The Cayley trick  is implemented by means of dynamic lifting. This trick computes all cells in a mixed subdivision.

Symmetric lifting 

allows to exploit permutation symmetries in the tuple of Newton polytopes. A symmetric subdivision is induced by lifting the points in the same orbit  up to the same height. The corresponding random coefficient start system has the same symmetric structure, so that in the homotopy, only the generating solution paths need to be traced.