Homotopy continuation methods have proven to be reliable for computing numerically approximations to all isolated solutions of polynomial systems. The performance of homotopy continuation methods depends heavily on the root count used for estimating the number of isolated solutions. Therefore, we have directed our attention to the development of root counting methods.

Two different classes of homotopy methods have been investigated, based on different notions of complexity: degree and geometric complexity. Product homotopy methods are based on the highest degree terms of each monomials. Polyhedral homotopies make use of the Newton polytopes of the polynomials in the system. While the first class is well suited for dense systems, sparse systems have to be solved by polyhedral homotopy methods.

To improve the performance of the classical homotopy based on the total degree, we proposed to apply nonlinear reduction. Hereby the system is reformulated into an equivalent one with lower degree polynomials by computing S-polynomials. By casting Bézout's theorem in multi-homogeneous space, frequently a more accurate root count than the total degree can be obtained. To exploit the multi-homogeneous structure, we first constructed interpolating multi-homogeneous homotopies. Later we derived more efficient Bézout number computations by exploiting the analogy with the solution of multi-homogeneous linear-product systems. This insight led us to a generalization of Bézout's theorem, where we used a set structure as basis for the root count. This root counting method proved to be more flexible and effective, especially for symmetric polynomial systems.

We have developed several polyhedral homotopy methods by elaborating four different lifting algorithms. First we implemented the algorithm Bernshtein gave in his proof. Nowadays, we call this implicit lifting. Later we applied the static lifting method of Huber and Sturmfels to symmetric polynomial systems. Symmetry forced us to extend static lifting with a recursive mechanism. To control the height of the lifting and to obtain consequently a stable polyhedral continuation, we developed the dynamic lifting algorithm. This algorithm enables incremental polynomial system solving.

We have implemented all investigated methods in Ada. The result is an integrated work bench whose tools offer various root counting and homotopy methods. We have tested the package extensively on a wide range of polynomial systems derived from various application fields. Hereby we have provided practical evidence that the investigated homotopy continuation methods are effective in solving polynomial systems.

Click here to download gzipped postscript version.