HOMotopy method for solving Polynomial Systems




HOM4PS-2.0 is a software package which implements the polyhedral homotopy continuation method for solving  polynomial systems in n equations with n variables, where n > 1. By Bernshtein’s combinatorial root count theorem [4], the polyhedral homotopies are established to approximate all the isolated zeros of a polynomial system using the continuation method [2][3]. Due to fewer homotopy paths, it yields a drastic improvement over the classical linear homotopies for solving sparse polynomial systems. Based on several sophisticated iteration criteria from Numerical Analysis and some good properties in Algebraic Geometry, all algorithms in the package are skillfully implemented, which plays an essential ingredient for achieving remarkable efficiency and robustness as reported in [1]. Consequently, it provides a useful tool for investigating solutions of polynomial systems.





[1] T. L. Lee, T. Y. Li and C. H. Tsai (2008), “HOM4PS-2.0, A software package for solving polynomial systems by the polyhedral homotopy continuation method”, Computing, 83, pp109-133.


[2] B. Huber and B. Sturmfels (1995), “A polyhedral method for solving sparse polynomial systems”, Math. Comp., 64, pp. 1541-1555.


[3] T. Y. Li (2003), “Solving polynomial systems by the homotopy continuation method”, Handbook of numerical analysis, Vol. XI, Edited by P. G. Ciarlet, North-Holland, Amsterdam.


[4] D. N. Bernshtein (1975), “The number of roots of a system of equations”, Functional Analysis and Appl., 9(3), pp. 183-185.





        Windows XP system

        Matlab interface

        Macintosh system

        Linux system