The homotopy continuation method: numerically implementable topological procedures

Alexander, J. C.; Yorke, James A.

doi:10.1090/S0002-9947-1978-0478138-5

The homotopy continuation method: numerically implementable topological procedures
HTML articles powered by AMS MathViewer

by J. C. Alexander and James A. Yorke PDF

Trans. Amer. Math. Soc. 242 (1978), 271-284 Request permission

Abstract:

The homotopy continuation method involves numerically finding the solution of a problem by starting from the solution of a known problem and continuing the solution as the known problem is homotoped to the given problem. The process is axiomatized and an algebraic topological condition is given that guarantees the method will work. A number of examples are presented that involve fixed points, zeroes of maps, singularities of vector fields, and bifurcation. As an adjunct, proofs using differential rather than algebraic techniques are given for the Borsuk-Ulam Theorem and the Rabinowitz Bifurcation Theorem.

References

J. F. Adams, Vector fields on spheres, Ann. of Math. (2) 75 (1962), 603–632. MR 139178, DOI 10.2307/1970213
J. C. Alexander, Bifurcation of zeroes of parametrized functions, J. Functional Analysis 29 (1978), no. 1, 37–53. MR 499933, DOI 10.1016/0022-1236(78)90045-9
J. C. Alexander, The additive inverse eigenvalue problem and topological degree, Proc. Amer. Math. Soc. 70 (1978), no. 1, 5–7. MR 487546, DOI 10.1090/S0002-9939-1978-0487546-3
J. C. Alexander and James A. Yorke, Global bifurcations of periodic orbits, Amer. J. Math. 100 (1978), no. 2, 263–292. MR 474406, DOI 10.2307/2373851

Parameterized functions, bifurcation, and vector fields on spheres

Calculating bifurcation invariants as homotopy elements of the general linear group

Shui Nee Chow, John Mallet-Paret, and James A. Yorke, Finding zeroes of maps: homotopy methods that are constructive with probability one, Math. Comp. 32 (1978), no. 143, 887–899. MR 492046, DOI 10.1090/S0025-5718-1978-0492046-9
B. Curtis Eaves, Homotopies for computation of fixed points, Math. Programming 3 (1972), 1–22. MR 303953, DOI 10.1007/BF01584975
B. Curtis Eaves, A short course in solving equations with PL homotopies, Nonlinear programming (Proc. Sympos., New York, 1975) SIAM-AMS Proc., Vol. IX, Amer. Math. Soc., Providence, R.I., 1976, pp. 73–143. MR 0401155
B. Curtis Eaves and Herbert Scarf, The solution of systems of piecewise linear equations, Math. Oper. Res. 1 (1976), no. 1, 1–27. MR 445792, DOI 10.1287/moor.1.1.1
Shmuel Friedland, On inverse multiplicative eigenvalue problems for matrices, Linear Algebra Appl. 12 (1975), no. 2, 127–137. MR 432672, DOI 10.1016/0024-3795(75)90061-0
Victor Guillemin and Alan Pollack, Differential topology, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. MR 0348781
Morris W. Hirsch, A proof of the nonretractibility of a cell onto its boundary, Proc. Amer. Math. Soc. 14 (1963), 364–365. MR 145502, DOI 10.1090/S0002-9939-1963-0145502-8
Morris W. Hirsch, Differential topology, Graduate Texts in Mathematics, No. 33, Springer-Verlag, New York-Heidelberg, 1976. MR 0448362, DOI 10.1007/978-1-4684-9449-5

Fiber bundles

A method of continuation for calculating a Brouwer fixed point

R. B. Kellogg, T. Y. Li, and J. Yorke, A constructive proof of the Brouwer fixed-point theorem and computational results, SIAM J. Numer. Anal. 13 (1976), no. 4, 473–483. MR 416010, DOI 10.1137/0713041
Herbert B. Keller, Numerical solution of bifurcation and nonlinear eigenvalue problems, Applications of bifurcation theory (Proc. Advanced Sem., Univ. Wisconsin, Madison, Wis., 1976) Publ. Math. Res. Center, No. 38, Academic Press, New York, 1977, pp. 359–384. MR 0455353
Harold W. Kuhn, Simplicial approximation of fixed points, Proc. Nat. Acad. Sci. U.S.A. 61 (1968), 1238–1242. MR 488010, DOI 10.1073/pnas.61.4.1238

A rigorous algorithm for fixed point computation

A rigorous algorithm for solving equations when existence is proved using topological degree

Yung Chen Lu, Singularity theory and an introduction to catastrophe theory, Universitext, Springer-Verlag, New York, 1976. With an introduction by Peter Hilton. MR 0461562
Gunter H. Meyer, On solving nonlinear equations with a one-parameter operator imbedding, SIAM J. Numer. Anal. 5 (1968), 739–752. MR 242366, DOI 10.1137/0705057
John W. Milnor, Topology from the differentiable viewpoint, University Press of Virginia, Charlottesville, Va., 1965. Based on notes by David W. Weaver. MR 0226651

Morse theory

L. Nirenberg, Topics in nonlinear functional analysis, Courant Institute of Mathematical Sciences, New York University, New York, 1974. With a chapter by E. Zehnder; Notes by R. A. Artino; Lecture Notes, 1973–1974. MR 0488102
Paul H. Rabinowitz, Some global results for nonlinear eigenvalue problems, J. Functional Analysis 7 (1971), 487–513. MR 0301587, DOI 10.1016/0022-1236(71)90030-9
Werner C. Rheinboldt, Numerical continuation methods for finite element applications, Formulations and computational algorithms in finite element analysis (U.S.-Germany Sympos., Mass. Inst. Tech., Cambridge, Mass., 1976) M.I.T. Press, Cambridge, Mass., 1977, pp. 599–631. MR 0474782

Fixed point computing methods

On the convergence rate of algorithms for solving equations that are based on methods of complementary pivoting

Herbert Scarf, The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math. 15 (1967), 1328–1343. MR 242483, DOI 10.1137/0115116
Stephen Smale, Exchange processes with price adjustment, J. Math. Econom. 3 (1976), no. 3, 211–226. MR 452565, DOI 10.1016/0304-4068(76)90009-4