Finding all isolated solutions to polynomial systems using HOMPACK

ABSTRACT

Although the theory of polynomial continuation has been established for over a decade (following the work of Garcia, Zangwill, and Drexler), it is difficult to solve polynomial systems using continuation in practice. Divergent paths (solutions at infinity), singular solutions, and extreme scaling of coefficients can create catastrophic numerical problems. Further, the large number of paths that typically arise can be discouraging. In this paper we summarize polynomial-solving homotopy continuation and report on the performance of three standard path-tracking algorithms (as implemented in HOMPACK) in solving three physical problems of varying degrees of difficulty. Our purpose is to provide useful information on solving polynomial systems, including specific guidelines for homotopy construction and parameter settings. The m-homogeneous strategy for constructing polynomial homotopies is outlined, along with more traditional approaches. Computational comparisons are included to illustrate and contrast the major HOMPACK options. The conclusions summarize our numerical experience and discuss areas for future research.

REFERENCES

• 1: BILLUPS, S. C. An augmented Jacobian matrix algorithm for tracking homotopy zero curves. M.S. thesis, Dept. of Computer Science, Virginia Polytechnic Institute and State Univ., Blacksburg, Va., Sept. 1985.
• 2: BRUNOVSK~, P., AND MERAVY, P. Solving systems of polynomial equations by bounded and real homotopy. Numer. Math. 43 (1984), 397-418.
• 3: CHOW, S. N., MALLET-PARET, J., AND YORKE, J. A. Finding zerosofmaps: Homotopy methods that are constructive with probability one. Math. Comput. 32 (1978), 887-899.
• 4: ~ A homotopy method for locating all zeros of a system of polynomials, in Functional Differential Equations and Approximation of Fixed Points, Lecture Notes in Math. #730, H. O. Peitgen and H. O. Walther, Eds., Springer-Verlag, 1979, 228-237.
• 5: DREXLER, F. J. Eine Methode zur Berechung s~izntlicher L6sunger yon Polynomgleichungessystemen. Numer. Math. 29 (1977), 45-58.
• 6: ~ A homotopy method for the calculation of zeros of zero-dimensional polynomial ideals. In Continuation Methods, H. G. Wacker (Ed.), Academic Press, NY, 1978, 69-93.
• 7: FISCHER, G. Complex Analytic Geometry. Lecture Notes in Mathematics No. 538, Springer- Verlag, New York, 1977.
• 8: FULTON, W. Intersection Theory. Springer-Verlag, New York, 1984.
• 9: CARCIA, C. B.~ AND LI, T. Y. On the number of solutions to polynomial systems of equations. SIAM J. Numer. Anal. 17 (1980), 540-546.
• 10: GARCIA, C. B., AND ZANGWILL, W. I. Global continuation methods for finding all solutions to polynomial systems of equations in N variables. Center for Math. Studies in Business and Economics Rep. No. 7755, University of Chicago, 1977.
• 11: Finding all solutions to polynomial systems and other systems of equations. Math. Programming 16 (1979), 159-176.
• 12: ~ An approach to homotopy and degree theory. Math. Oper. Res. 4 (1979), 390-405.
• 13: ~ Determining all solutions to certain systems of nonlinear equations. Math. Oper. Res. 4 (1979), 1-14.
• 14: ~ Pathways to Solutions, Fixed Points, and Equilibria. Prentice-Hall, Englewood Cliffs, N J, 1981.
• 15: GRIFFITHS, P., AND HARRIS, J. Principles of Algebraic Geometry. John Wiley and Sons, New York, 1978.
• 16: GUILLEMIN, V., AND POLLACK, A. Differential Topology. Prentice-Hall, Englewood Cliffs, NJ, 1974.
• 17: JENKINS, M. A., AND TRAUB, J. F. A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration. Numer. Math. 14 (1970), 252-263.
• 18: GRIEWANK, A. On solving nonlinear equations with simple singularities or nearly singular solutions. SIAM Rev. 27 (1985), 537-563.
• 19: Tien-Yien Li , Tim Sauer , James A. Yorke, Numerical solution of a class of deficient polynomial systems, SIAM Journal on Numerical Analysis, v.24 n.2, p.435-451, April 1987 [doi>10.1137/0724032]
• 20: Keith Meintjes , Alexander P Morgan, A methodology for solving chemical equilibrium systems, Applied Mathematics and Computation, v.22 n.4, p.333-361, June 1987 [doi>10.1016/0096-3003(87)90076-2]
• 21: Alexander P. Morgan, A Method for Computing All Solutions to Systems of Polynomials Equations, ACM Transactions on Mathematical Software (TOMS), v.9 n.1, p.1-17, March 1983 [doi>10.1145/356022.356023]
• 22: ~ A transformation to avoid solutions at infinity for polynomial systems. Appl. Math. Comput. 18 (1986), 77-86.
• 23: ~ A homotopy for solving polynomial systems. Appl. Math. Comput. 18 (1986), 87-92.
• 24: ~ Solving Polynomial Systems Using Continuation for Scientific and Engineering Problems. Prentice-Hall, Englewood Cliffs, NJ, 1987.
• 25: Alexander Morgan , Andrew Sommese, A homotopy for solving general polynomial systems that respects m-homogenous structures, Applied Mathematics and Computation, v.24 n.2, p.101-113, Nov. 1987 [doi>10.1016/0096-3003(87)90063-4]
• 26: Alexander Morgan , Andrew Sommese, Computing all solutions to polynomial systems using homotopy continuation, Applied Mathematics and Computation, v.24 n.2, p.115-138, Nov. 1987 [doi>10.1016/0096-3003(87)90064-6]
• 27: Alexander P. Morgan , Andrew J. Sommese, Coefficient-parameter polynomial continuation, Applied Mathematics and Computation, v.29 n.2, p.123-160, Jan. 1989 [doi>10.1016/0096-3003(89)90099-4]
• 28: MORGAN, A. F., AND SARRAGA, R. F. A method for computing three surface intersection points in GMSOLID. ASME paper 82-DET-41 (1982). Also available as Res. Pub. GMR- 3964, Math. Dept., G. M. Research Lab., Warren, Mi. 48090, 1981.
• 29: RICHTER, S., AND DE CARLO, R. A homotopy method for eigenvalue assignment using decentralized state feedback. IEEE Trans. Auto. Control AC-29 (1984), 148-158.
• 30: Werner C. Rheinboldt , John V. Burkardt, Algorithm 596: a program for a locally parameterized, ACM Transactions on Mathematical Software (TOMS), v.9 n.2, p.236-241, June 1983 [doi>10.1145/357456.357461]
• 31: SAFONOV, M. G. Exact calculation of the multivariable structured-singular-value stability margin. IEEE Control and Decision Conference, Las Vegas, NV, Dec. 12-14, 1984.
• 32: SHAFAREVICH, 1. R. Basic Algebraic Geometry. Springer-Verlag, New York, 1977.
• 33: TSAI, L.-W., AND MORGAN, A. P. Solving the kinematics of the most general six- and fivedegree-of-freedom manipulators by continuation methods. ASME J. of Mechanisms, Transmissions and Automation in Design 107 (1985), 48-57.
• 34: WATSON~ L. T. A globally convergent algorithm for computing fixed points of C2 maps. Appl. Math. Comput. 5 (1979), 297-311.
• 35: Layne T Watson, Numerical linear algebra aspects of globally convergent homotopy methods, SIAM Review, v.28 n.4, p.529-545, Dec. 1986 [doi>10.1137/1028157]
• 36: Layne T. Watson , Stephen C. Billups , Alexander P. Morgan, ALGORITHM 652: HOMPACK: a suite of codes for globally convergent homotopy algorithms, ACM Transactions on Mathematical Software (TOMS), v.13 n.3, p.281-310, Sept. 1987 [doi>10.1145/29380.214343]
• 37: Layne T. Watson , Dan Fenner, Algorithm 555: Chow-Yorke Algorithm for Fixed Points or Zeros of C2 Maps [C5], ACM Transactions on Mathematical Software (TOMS), v.6 n.2, p.252-259, June 1980 [doi>10.1145/355887.355899]
• 38: VAN DER WAERDEN, B. L. Algebra. Vols. 1, 2, Frederick Ungax Pub. Co., New York, 1970.
• 39: WRIGHT, A. H. Finding all solutions to a system of polynomial equations. Math. Comp. 44 (1985), 125-133.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

      Nouns: HOMPACK

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for; Systems of equations

General Terms:
Algorithms, Theory