×

HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method. (English) Zbl 1167.65366

Summary: HOM4PS-2.0 is a software package in FORTRAN 90 which implements the polyhedral homotopy continuation method for solving polynomial systems. It updates its original version HOM4PS in three key aspects: (1) a new method for finding mixed cells; (2) combining the polyhedral and linear homotopies in one step; (3) a new way of dealing with curve jumping. Numerical results show that this revision leads to a spectacular speed-up, ranging up to 1950s, over its original version on all benchmark systems, especially for large ones. It surpasses the existing packages in finding isolated zeros, such as PHCpack [J. Verschelde, ACM Trans. Math. Softw. 25, No. 2, 251–276 (1999; Zbl 0961.65047)] PHoM [T. Gunji et al., Computing 73, No. 1, 57–77 (2004; Zbl 1061.65041)] and Bertini [D. J. Bates et al., in: Stillman, Michael E. (ed.) et al., Software for algebraic geometry. Papers of a workshop, Minneapolis, MN, USA, October 23–27, 2006. New York, NY: Springer. The IMA Volumes in Mathematics and its Applications 148, 1–14 (2008; Zbl 1143.65344), available at http://www.nd.edu/~sommese/bertini], in speed by big margins.

MSC:

65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] Bates DJ, Hauenstein JD, Sommese AJ, Wampler CW Bertini: Software for numerical algebraic geometry. Available at http://www.nd.edu/\(\sim\)sommese/bertini
[2] Bates DJ, Hauenstein JD, Sommese AJ, Wampler CW (2008) Adaptive multiprecision path tracking. SIAM J Numer Anal 46(2): 722–746 · Zbl 1162.65026
[3] Bernshtein DN (1975) The number of roots of a system of equations. Funct Anal Appl 9(3): 183–185 · Zbl 0328.32001
[4] Björk G, Fröberg R (1991) A faster way to count the solutions of inhomogeneous systems of algebraic equations. J Symb Comput 12(3): 329–336 · Zbl 0751.12001
[5] Boege W, Gebauer R, Kredel H (1986) Some examples for solving systems of algebraic equations by calculating Groebner bases. J Symb Comput 2: 83–98 · Zbl 0602.65032
[6] Cohn H (1982) An explicit modular equation in two variables and Hilbert’s twelfth problem. Math Comp 38: 227–236 · Zbl 0491.12009
[7] Dai T, Kim S, Kojima M (2003) Computing all nonsingular solutions of cyclic-n polynomial using polyhedral homotopy continuation methods. J Comput Appl Math 152(1–2): 83–97 · Zbl 1018.65068
[8] Gao T, Li TY (2000) Mixed volume computation via linear programming. Taiwan J Math 4: 599–619 · Zbl 0997.65081
[9] Gao T, Li TY (2003) Mixed volume computation for semi-mixed systems. Discrete Comput Geom 29(2): 257–277 · Zbl 1052.68131
[10] Gao T, Li TY, Wu M (2005) Algorithm 846: MixedVol: a software package for mixed volume computation. ACM Trans Math Softw 31(4): 555–560 · Zbl 1136.65320
[11] Gunji T, Kim S, Kojima M, Takeda A, Fujisawa K, Mizutani T (2004) PHoM–a polyhedral homotopy continuation method. Computing 73: 57–77 · Zbl 1061.65041
[12] Huber B, Sturmfels B (1995) A polyhedral method for solving sparse polynomial systems. Math Comp 64: 1541–1555 · Zbl 0849.65030
[13] Huber B, Verschelde J (1998) Polyhedral end games for polynomial continuation. Numer Algorithms 18(1): 91–108 · Zbl 0933.65057
[14] Kim S, Kojima M (2004) Numerical stability of path tracing in polyhedral homotopy continuation methods. Computing 73: 329–348 · Zbl 1061.65042
[15] Kuo YC, Li TY (2008) Determining dimension of the solution component that contains a computed zero of a polynomial system. J Math Anal Appl 338(2): 840–851 · Zbl 1133.65028
[16] Lee TL, Li TY Mixed volume computation. A revisit (submitted)
[17] Leykin A, Verschelde J, Zhao A (2006) Newton’s method with deflation for isolated singularities of polynomial systems. Theor Comput Sci 359(1–3): 111–122 · Zbl 1106.65046
[18] Leykin A, Verschelde J, Zhao A (2007) Evaluation of Jacobian matrices for Newton’s method with deflation to approximate isolated singular solutions of polynomial systems. Symb Numer Comput 269–278 · Zbl 1117.65074
[19] Leykin A, Verschelde J, Zhao A (2008) Higher-order deflation for polynomial systems with isolated singular solutions. In: IMA: algorithms in algebraic geometry, vol 146. Springer, Heidelberg, pp 79–97 · Zbl 1138.65038
[20] Li TY (1997) Numerical solution of multivariate polynomial systems by homotopy continuation methods. Acta Numer 6: 399–436 · Zbl 0886.65054
[21] Li TY (1999) Solving polynomial systems by polyhedral homotopies. Taiwan J Math 3: 251–279 · Zbl 0945.65052
[22] Li TY (2003) Solving polynomial systems by the homotopy continuation method. Handbook of numerical analysis, vol XI. North-Holland, Amsterdam, pp 209–304
[23] Li TY, Li X (2001) Finding mixed cells in the mixed volume computation. Found Comput Mathem 1: 161–181 · Zbl 1012.65019
[24] Li TY, Sauer T, Yorke JA (1989) The cheaters homotopy: an efficient procedure for solving systems of polynomial equations. SIAM J Numer Anal 26: 1241–1251 · Zbl 0689.65032
[25] Li TY, Zeng Z (2005) A rank-revealing method with updating, downdating, and applications. SIAM J Matrix Anal Appl 26: 918–946 · Zbl 1114.15004
[26] Mizutani T, Takeda A, Kojima M (2007) Dynamic enumeration of all mixed cells. Discrete Comput Geom 37: 351–367 · Zbl 1113.65055
[27] Morgan AP (1987) Solving polynomial systems using continuation for engineering and scientific problems. Prentice-Hall, New Jersey · Zbl 0733.65031
[28] Morgan AP, Sommese AJ (1992) Coefficient-parameter polynomial continuation (Errata: Appl Math Comput 51:207). Appl Math Comput 29: 123–160 · Zbl 0664.65049
[29] Morgan AP, Sommese AJ, Wampler CW (1992) A power series method for computing singular solutions to nonlinear analytic systems. Numer Math 63(3): 1779–1792 · Zbl 0756.65079
[30] Noonburg VW (1989) A neural network modeled by an adaptive Lotka–Volterra system. SIAM J Appl Math 49: 1779–1792 · Zbl 0684.92008
[31] Sommese A, Verschelde J, Wampler C (2001) Numerical decomposition of the solution sets of polynomial systems into irreducible components. SIAM J Numer Anal 38(6): 2022–2046 · Zbl 1002.65060
[32] Sommese A, Wampler C (2005) The numerical solution of polynomial systems arising in engineering and science. World Scientific Publishing, Hackensack · Zbl 1091.65049
[33] Traverso C The PoSSo test suite at http://www.inria.fr/saga/PO .
[34] Verschelde J (1999) Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation. ACM Trans Math Softw 25:251–276. Software available at http://www.math.uic.edu/\(\sim\)jan · Zbl 0961.65047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.