PHC and MVC: two Programs for Solving Polynomial Systems
by Homotopy Continuation

Jan Verschelde

Abstract:

Two interactive programs will be presented to deal with computing all isolated complex solutions to a system of multivariate polynomials with complex coefficients. They represent recent research progress in root counting and polynomial system solving.

During the past two decades, homotopy continuation methods have proven to be numerically reliable and efficient for solving polynomial systems. The program PHC (Polynomial Homotopy Continuation) offers an implementation of product and polyhedral homotopy methods. Product homotopies are based on generalizations of Bézout's theorem for counting the number of solutions of dense systems. Based on Bernshtein's theorem, polyhedral homotopy methods have been developed to exploit the sparse structure of the system. The second part of PHC consists of Predictor-Corrector continuation methods for tracking the solution paths which extend the solution set of the start system to the solution set of the target system.

A recent computational break through in solving sparse polynomial systems has been realized by applying mixed volumes as root count. The program MVC (Mixed Volume Computation) contains not only the algorithm Bernshtein used in his proof, but also the more general lifting algorithm developed by Huber and Sturmfels. As various lifting functions have been implemented, it is possible to explore the geometry of the mixed subdivisions and to develop efficient homotopies which enable to exploit the symmetric structure of the system. Recently, the dynamic lifting algorithm, which leads to an incremental solver, has enlarged the possibilities of the program significantly.

The binaries of PHC and MVC for DECStations DS 3000 will be made publicly available. The programs remain under continuing development, in order to keep track of the recent advances in this rapidly growing research area. Future releases will include executables for other hardware platforms and the source code of the programs, which are written in Ada.

Proceedings of the POSSO Workshop on Software pages 165-176. Edited by J.-C. Faug\`ere, J. Marchand, R. Rioboo, Paris 1-4 March 1995.