×

zbMATH — the first resource for mathematics

Globally convergent homotopy methods: A tutorial. (English) Zbl 0689.65033
The paper begins by introducing globally convergent homotopy methods with an example inverse problem related to cantilever beams. The next section deals with theory, and concentrate on conditions for which, in various practical settings, the homotopy path will lead from the initial guess to the solution. Theorems related to Brouwer fixed points, general zero- finding, optimization, and two-point boundary value problems discretized with shooting, finite differences, collocation, and finite elements are given.
The third section deals with path-following algorithms for problems with dense Jacobian matrices; it treats ODE-based algorithms, normal flow algorithms, and augmented Jacobian matrix algorithms. Substantial detail is given, but not so much that clarity is sacrificed. The fourth section provides an overview of the software package HOMPACK. This package contains instantiations of the three path-following algorithms for three path-following algorithms for three problem types and for both dense and sparse Jacobian matrices. Lists of the HOMPACK routines grouped by function occur.
Section 5 contains pointers to references in which applications are discussed. Section 6 discusses parallel implementation of the methods on hypercubes Experimental results for polynomial systems, in which each path is assigned to a node, are given for the Intel iPSC-32 and a test set from General Motors. There are 83 references.
Reviewer: B.Kearfott

MSC:
65H10 Numerical computation of solutions to systems of equations
Software:
minpack; HOMPACK; PITCON
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alexander, J.C., The topological theory of an imbedding method, (), 37-68
[2] Alexander, J.C.; Yorke, J.A., The homotopy continuation method: numerically implementable topological procedures, Trans. amer. math. soc., 242, 271-284, (1978) · Zbl 0424.58003
[3] Alexander, J.C.; Li, T.-Y.; Yorke, J.A., Piecewise smooth homotopies, (), 1-14 · Zbl 0519.55001
[4] Allgower, E.; Georg, K., Simplical and continuation methods for approximating fixed points, SIAM rev., 22, 28-85, (1980) · Zbl 0432.65027
[5] Billups, S.C., An augmented Jacobian matrix algorithm for tracking homotopy zero curves, ()
[6] Boggs, P., The solution of nonlinear systems of equations by A-stable integration techniques, SIAM J. numer. anal., 8, 767-785, (1971) · Zbl 0209.47002
[7] Businger, P.; Golub, G.H., Linear least squares solutions by Householder transformations, Numer. math., 7, 269-276, (1965) · Zbl 0142.11503
[8] Chow, S.N.; Mallet-Paret, J.; Yorke, J.A., Finding zeros of maps: homotopy methods that are constructive with probability one, Math. comp., 32, 887-899, (1978) · Zbl 0398.65029
[9] Chow, S.N.; Mallet-Paret, J.; Yorke, J.A., A homotopy method for locating all zeros of a system of polynomials, (), 228-237
[10] Davidenko, D.F., On the approximate solution of systems of nonlinear equations, Ukrain. mat. ž, 5, 196-206, (1953)
[11] Dennis, J.E.; Schnabel, R., Numerical methods for unconstrained optimization and nonlinear equations, (1983), Prentice-Hall Englewood Cliffs, NJ · Zbl 0579.65058
[12] Dunyak, J.P.; Junkins, J.L.; Watson, L.T., Robust nonlinear least squares estimation using the Chow-Yorke homotopy method, J. guidance, control, dynamics, 7, 752-755, (1984) · Zbl 0579.65062
[13] Eaves, D.C., Homotopies for the computation of fixed points, Math. programming, 3, 1-22, (1972) · Zbl 0276.55004
[14] Eaves, B.C.; Saigal, R., Homotopies for computation of fixed points on unbounded regions, Math. programming, 3, 225-237, (1972) · Zbl 0258.65060
[15] Fadeev, D.K.; Fadeeva, V.N., Computational methods of linear algebra, (1963), Freeman London
[16] Georg, K., Private communication, (1981)
[17] Georg, K., A note on stepsize control for numerical curve following, (), 145-154
[18] Georg, K., Numerical integration of the davidenko equation, () · Zbl 0474.65038
[19] Gill, P.E.; Murray, W., Newton type methods for unconstrained and linearly constrained optimization, Math. programming, 7, 311-350, (1974) · Zbl 0297.90082
[20] M. W. H{\scERUSKA}, L.T. W{\scATSON}, {\scAND} K.K. S{\scANKARA}, Micropolar flow past a porous stretching sheet, Comput. & Fluids, to appear.
[21] Hestenes, M.R., The conjugate gradient method for solving linear systems, (), 83-102
[22] Kamat, M.P.; Watson, L.T.; Venkayya, V.B., A quasi-Newton versus a homotopy method for nonlinear structural analysis, Comput. & structures, 17, 579-585, (1983) · Zbl 0511.73097
[23] Keller, H.B., Numerical solution of two-point boundary value problems, (1976), Society for Industrial and Applied Mathematics Philadelphia
[24] Keller, H.B., Numerical solution of bifurcation and nonlinear eigenvalue problems, () · Zbl 0581.65043
[25] Klopfenstein, R.W., Zeros of nonlinear functions, J. assoc. comput. mech., 8, 336-373, (1961) · Zbl 0099.10901
[26] Kubicek, M., Dependence of solutions of nonlinear systems on a parameter, ACM-toms, 2, 98-107, (1976) · Zbl 0317.65019
[27] Kwok, H.H.; Kamat, M.P.; Watson, L.T., Location of stable and unstable equilibrium configurations using a model trust region quasi-Newton method and tunnelling, Comput. & structures, 21, 909-916, (1985) · Zbl 0587.73131
[28] R. M{\scEJIA}, CONKUB: A conversational path-follower for systems of nonlinear equations, J. Comput. Phys., to appear.
[29] Menzel, R.; Schwetlick, H., Zur Lösung parameterabhängiger nichtlinearer gleichungen mit singulären Jacobi-matrizen, Numer. math., 30, 65-79, (1978) · Zbl 0425.65032
[30] Merrill, O., Applications and extensions of an algorithm to compute fixed points of upper semicontinuous mappings, ()
[31] Meyer, G., On solving nonlinear equations with a one-parameter operator embedding, SIAM J. numer. anal., 5, 739-752, (1968) · Zbl 0182.48701
[32] Moré, J.J.; Garbow, B.S.; Hillstrom, K.E., User guide for MINPACK-1, ()
[33] Morgan, A.P., A transformation to avoid solutions at infinity for polynomial systems, Appl. math. comput., 18, 77-86, (1986) · Zbl 0597.65045
[34] Morgan, A.P., A homotopy for solving polynomial systems, Appl. math. comput., 18, 87-92, (1986) · Zbl 0597.65046
[35] Morgan, A.P.; Watson, L.T., Solving nonlinear equations on a hypercube, Proc. ASCE structures congress, (1986), New Orleans, Sept.
[36] Rheinboldt, W.C.; Den Héyér, C., On steplength algorithms for a class of continuation methods, SIAM J. numer. anal., 18, 925-947, (1981) · Zbl 0472.65042
[37] Rheinboldt, W.C., On the computation of critical boundaries on equilibrium surfaces, SIAM J. numer. anal., 19, 653-669, (1982) · Zbl 0489.65033
[38] Rheinboldt, W.C.; Melhem, R., A comparison of methods for determining turning points of nonlinear equations, Computing, 29, 103-114, (1982) · Zbl 0479.65032
[39] Rheinboldt, W.C.; Burkardt, J.V., Algorithm 596: A program for a locally parameterized continuation process, ACM trans. math. software, 9, 236-241, (1983)
[40] Riks, E., An incremental approach to the solution of snapping and buckling problems, Internat. J. solids structures, 15, 529-551, (1979) · Zbl 0408.73040
[41] Saigal, R., On the convergence rate of algorithms for solving equations that are based on methods of complementary pivoting, Math. operations res., 2, 108-124, (1977) · Zbl 0395.90082
[42] Saigal, R.; Todd, M.J., Efficient acceleration techniques for fixed point algorithms, SIAM J. numer. anal., 15, 997-1007, (1978) · Zbl 0396.65022
[43] Saigal, R., An efficient procedure for traversing large pieces in fixed point algorithms, (), 239-248
[44] Sankara, K.K.; Watson, L.T., Micropolar flow past a stretching sheet, Z. angew. math. phys., 36, 845-853, (1985) · Zbl 0585.76006
[45] Scarf, H., The approxiamtion of fixed points of a continuous mapping, SIAM J. appl. math., 15, 1328-1343, (1967) · Zbl 0153.49401
[46] Scott, M.R., Invariant imbedding and its applications to ordinary differential equations, (1973), Addison-Wesley Reading, MA
[47] Shampine, L.F.; Gordon, M.K., Computer solution of ordinary differential equations: the initial value problem, (1975), W.H. Freeman San Francisco · Zbl 0347.65001
[48] Smale, S., Convergent process of price adjustment and global Newton methods, J. math. econom., 3, 107-120, (1976) · Zbl 0354.90018
[49] Wang, C.Y.; Watson, L.T., Squeezing of a viscous fluid between elliptic plates, Appl. sci. res., 35, 195-207, (1979) · Zbl 0414.76025
[50] Wang, C.Y., Viscous flow between rotating disc with injection on the porous disc, Z. angew. math. phys., 30, 773-787, (1979) · Zbl 0426.76032
[51] Wang, C.Y., On the large deformations of C-shaped springs, Internat. J. mech. sci., 22, 395-400, (1980) · Zbl 0435.73044
[52] Wang, C.Y., Theory of the constant force spring, J. appl. mech., 47, 956-958, (1980)
[53] Wang, C.Y., The fluid-filled cylindrical membrane container, J. engrg. math., 15, 81-88, (1981) · Zbl 0459.73037
[54] Wang, C.Y., Equilibrium of heavy elastic cylindrical shells, J. appl. mech., 48, 582-586, (1981) · Zbl 0465.73085
[55] Wang, C.Y., The elastic catenary, Internat. J. mech. sci., 24, 349-357, (1982) · Zbl 0482.73033
[56] Wang, C.Y., Free rotation of a circular ring about a diameter, Z. angew. math. phys., 34, 13-24, (1983) · Zbl 0505.73034
[57] Wang, C.Y.; Watson, L.T.; Kamat, M.P., Buckling, postbuckling and the flow through a tethered elastic cylinder under external pressure, J. appl. mech., 50, 13-18, (1983) · Zbl 0511.73040
[58] Watson, L.T.; Li, T.Y.; Wang, C.Y., Fluid dynamics of the elliptic porous slider, J. appl. mech., 45, 435-436, (1978)
[59] Watson, L.T.; Wang, C.Y., A homotopy method applied to elastica problems, Internat. J. solids structures, 17, 29-37, (1981) · Zbl 0452.73071
[60] Watson, L.T., Deceleration of a rotating disc in a viscous fluid, Phys. fluids, 22, 2267-2269, (1979) · Zbl 0418.76024
[61] Watson, L.T., The circular leaf spring, Acta mech., 40, 25-32, (1981)
[62] Watson, L.T., Hanging an elastic ring, Internat. J. mech. sci., 23, 161-168, (1981) · Zbl 0471.73055
[63] Watson, L.T., Overhang of a heavy elastic sheet, Z. angew. math. phys., 33, 17-23, (1982) · Zbl 0483.73050
[64] Watson, L.T., Periodically supported heavy elastic sheet, J. engrg. mech., 109, 811-820, (1983)
[65] Watson, L.T., The equilibrium states of a heavy rotating column, Internat. J. solids structures, 19, 653-658, (1983) · Zbl 0517.73045
[66] Watson, L.T.; Yang, W.H., Optimal design by a homotopy method, Applicable anal., 10, 275-284, (1980) · Zbl 0448.73083
[67] Watson, L.T., Methods for optimal engineering design problems based on globally convergent methods, Comput. & structures, 13, 115-119, (1981) · Zbl 0462.65032
[68] Watson, L.T.; Fenner, D., Chow-Yorke algorithm for fixed points or zeros of C^{2} maps, ACM toms, 6, 252-260, (1980) · Zbl 0445.65033
[69] Watson, L.T., A globally convergent algorithm for computing fixed points of C^{2} maps, Appl. math. comput., 5, 297-311, (1979) · Zbl 0445.65032
[70] Watson, L.T., Numerical study of porous channel flow in a rotating system by a homotopy method, J. comput. appl. math., 7, 21-26, (1981) · Zbl 0452.76025
[71] Watson, L.T., Computational experience with the Chow-Yorke algorithm, Math. programming, 19, 92-101, (1980) · Zbl 0436.90096
[72] Watson, L.T., Fixed points of C^{2} maps, J. comput. appl. math., 5, 131-140, (1979) · Zbl 0445.65031
[73] Watson, L.T., Solving the nonlinear complementarity problem by a homotopy method, SIAM J. control optim., 17, 36-46, (1979) · Zbl 0407.90083
[74] 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, 394-401, (1979) · Zbl 0438.65069
[75] Watson, L.T., Solving finite difference approximations to nonlinear two-point boundary value problems by a homotopy method, SIAM J. sci. stat. comput., 1, 467-480, (1980) · Zbl 0456.65025
[76] Watson, L.T., Engineering applications of the Chow-Yorke algorithm, Appl. math. comput., 9, 111-133, (1981) · Zbl 0481.65029
[77] Watson, L.T., Numerical linear algebra aspects of globally convergent homotopy methods, () · Zbl 0608.65028
[78] Watson, L.T.; Holzer, S.M.; Hansen, M.C., Tracking nonlinear equilibrium paths by a homotopy method, Nonlinear anal., 7, 1271-1282, (1983) · Zbl 0538.65029
[79] Watson, L.T.; Sankara, K.K.; Mounfield, L.C., Deceleration of a porous rotating disk in a viscous fluid, Internat. J. engrg. sci., 23, 131-137, (1985)
[80] Watson, L.T.; Kamat, M.P.; Reaser, M.H., A robust hybrid algorithm for computing multiple equilibrium solutions, Engrg. comput., 2, 30-34, (1985)
[81] Watson, L.T.; Scott, M.R., Solving spline collocation approximations to nonlinear two-point boundary value problems by a homotopy method, () · Zbl 0635.65099
[82] Watson, L.T.; Billups, S.C.; Morgan, A.P., HOMPACK: A suite of codes for globally convergent homotopy algorithms, () · Zbl 0626.65049
[83] Watson, L.T.; Scott, L.R., Solving Galerkin approximations to nonlinear two-point boundary value problems by a globally convergent homotopy method, () · Zbl 0645.65043
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.