Algorithm 652: HOMPACK: a suite of codes for globally convergent homotopy algorithms

ABSTRACT

There are algorithms for finding zeros or fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, i.e., with probability one. The essence of all such algorithms is the construction of an appropriate homotopy map and then tracking some smooth curve in the zero set of this homotopy map. HOMPACK provides three qualitatively different algorithms for tracking the homotopy zero curve: ordinary differential equation-based, normal flow, and augmented Jacobian matrix. Separate routines are also provided for dense and sparse Jacobian matrices. A high-level driver is included for the special case of polynomial systems.

REFERENCES

• 1: BILLUPS, S.C. An augmented Jacobian matrix algorithm for tracking homotopy zero curves. Master's thesis, Dept. of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, Va., Sept. 1985.
• 2: BRUNOVSKY, P., AND MERAV~', P. Solving systems of polynomial equations by bounded and real homotopy. Numer. Math. 43 (1984), 397-418.
• 3: BUSINGER, P., AND GOLUB, G.H. Linear least squares solutions by Householder transformations. Numer. Math. 7 (1965), 269-276.
• 4: CHAN, T. F., AND SHAD, Y. Iterative methods for solving bordered systems with applications to continuation methods. SIAM J. Sci. Star. Comput. 6 (1985), 438-451.
• 5: CHOW, S. N., MALLET-PARET, J., AND YORKE, J.A. Finding zeros of maps: Homotopy methods that are constructive with probability one. Math. Cornput. 32 (1978), 887-899.
• 6: CHOW, S. N., MALLET-PARET, J. AND YORKE, J.A. A homotopy method for locating all zeros of a system of polynomials, in Functional Differential Equations and Approximation of Fixed Points. Lecture Notes in Mathematics Vol. 730. H. O. Peitgen and H. O. Walther, Eds. Springer- Verlag, New York, 1979, 228-237.
• 7: CRAIG, E. J. Iteration procedures for simultaneous equations. Ph.D. dissertation, MIT, Cambridge, 1954.
• 8: J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
• 9: FADEEV, D. K. AND FADEEVA, V. N. Computational Methods of Linear Algebra. Freeman, London, 1963.
• 10: GARCIA, C. B., AND ZANGWlLL, W.I. Finding all solutions to polynomial systems and other systems of equations. Math. Program. 16 (1979), 159-176.
• 11: GILL, P. E., AND MURRAY, W. Newton type methods for unconstrained and linearly constrained optimization. Math. Program. 7 (1974), 311-350.
• 12: HASELGROVE, C.B. A solution of nonlinear equations and of differential equations with twopoint boundary conditions. Comput. J. 4 (1961), 255-259.
• 13: HESTENES, M.R. The conjugate gradient method for solving linear systems. In Proceedings of the Symposium on Applied Mathematics, 6, Numer. Anal., AMS, New York, 1956, 83-102.
• 14: Milan Kubíček, Algorithm 502: Dependence of Solution of Nonlinear Systems on a Parameter [C5], ACM Transactions on Mathematical Software (TOMS), v.2 n.1, p.98-107, March 1976 [doi>10.1145/355666.355675]
• 15: MATTHIES, H., AND STRANG, G. The solution of nonlinear finite element equations. Int. J. Numer. Math. Eng., 14 (1979), 1613-1626.
• 16: 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]
• 17: R Mejia, CONKUB: A conversational path-follower for systems of nonlinear equations, Journal of Computational Physics, v.63 n.1, p.67-84, March 1986 [doi>10.1016/0021-9991(86)90084-7]
• 18: MENZEL, R., AND SCHWETLICK, H. Zur LSsung parameterabh~ingiger nichtlinearer Gleichungen mit singul~iren Jacobi-Matrizen. Numer. Math. 30 (1978), 65-79.
• 19: MORGAN, A.P. A transformation to avoid solutions at infinity for polynomial systems. Appl. Math. Comput. 18 (1986), 77-86.
• 20: MORGAN, A.P. Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems. Prentice-Hall, Englewood Cliffs, N.J., 1987.
• 21: 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]
• 22: RHEINBOLDT, W. C. Numerical analysis of continuation methods for nonlinear structural problems. Comput. Struct. 13 (1981), 103-113.
• 23: Werner C. Rheinboldt, Numerical analysis of parametrized nonlinear equations, Wiley-Interscience, New York, NY, 1986
• 24: 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]
• 25: SHAMPINE, L. F., AND GORDON, M.K. Computer Solution of Ordinary Differential Equations: The Initial Value Problem. W. H. Freeman, San Francisco, 1975.
• 26: 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. Mech. Transmissions, Aut. Des. 107 (1985), 48-57.
• 27: VAN DER WAERDEN, B.L. Modern Algebra, Vols. 1 and 2. Frederick Ungar, New York, 1953.
• 28: WATSON, L.T. A globally convergent algorithm for computing fixed points of C2 maps. Appl. Math. Comput. 5 (1979), 297-311.
• 29: WATSON, L.T. Fixed points of C2 maps. Jo Comput. Appl. Math. 5 (1979), 131-140.
• 30: WATSON, L.T. Solving the nonlinear complementarity problem by a homotopy method. SIAM J. Contr. Optim. 17 {1979), 36-46.
• 31: WATSON, L.T. An algorithm that is globally convergent with probability one for a class of nonlinear two-point boundary value problems. SIAM J. Numer. Anal. 16 (1979), 394-401.
• 32: WATSON, L.T. Computational experience with the Chow-Yorke algorithm. Math. Program. 19 (1980), 92-101.
• 33: WATSON, L.T. Solving finite difference approximations to nonlinear two-point boundary value problems by a homotopy method. SIAM J. Sci. Stat. Computo 1 (1980), 467-480.
• 34: WATSON, L.T. Engineering applications of the Chow-Yorke algorithm. Appl. Math. Comput. 9 (1981), 111-133.
• 35: WATSON, L.T. Numerical linear algebra aspects of globally convergent homotopy methods. Tech. Rep. TR-85-14, Dept. of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, Va., 1985.
• 36: 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]
• 37: WATSON, L. T., KAMAT, M. P., AND REASER, M.H. A robust hybrid algorithm for computing multiple equilibrium solutions. Eng. Cornput. 2 (1985), 30-34.
• 38: WATSON, L. T., AND SCOTT, M.R. Solving spline collocation approximations to nonlinear twopoint boundary value problems by a homotopy method. Tech. Rep. TR-84-15, Dept. of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, Va., 1984.
• 39: WRIGHT, A.H. Finding all solutions to a system of polynomial equations. Math. Comput. 44 (1985), 125-133.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms

Keywords:
Chow-Yorke algorithm, continuation method, curve tracking, fixed point, globally convergent, homotopy methods, nonlinear systems, polynomial systems, zero