The homotopy continuation method: numerically implementable topological procedures

Authors:
J. C. Alexander and James A. Yorke

Journal:
Trans. Amer. Math. Soc. **242** (1978), 271-284

MSC:
Primary 55C20; Secondary 58C99, 65H10

DOI:
https://doi.org/10.1090/S0002-9947-1978-0478138-5

MathSciNet review:
0478138

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**[1]**J. F. Adams,*Vector fields on spheres*, Ann. of Math. (2)**75**(1962), 603-632. MR**0139178 (25:2614)****[2]**J. C. Alexander,*Bifurcation of zeroes of parameterized functions*, J. Functional Analysis (to appear). MR**499933 (80j:58023)****[3]**-,*The additive inverse eigenvalue problem and topological degree*, Proc. Amer. Math. Soc. (to appear). MR**487546 (80a:55002)****[4]**J. C. Alexander and J. A. Yorke,*Global bifurcation of periodic orbits*, Amer. J. Math. (to appear). MR**0474406 (57:14046)****[5]**-,*Parameterized functions, bifurcation, and vector fields on spheres*(to appear).**[6]**-,*Calculating bifurcation invariants as homotopy elements of the general linear group*, J. Pure Appl. Algebra (to appear).**[7]**S. N. Chow, J. Mallet-Paret and J. A. Yorke,*Finding zeroes of maps: homotopy methods that are constructive with probability one*(to appear). MR**492046 (80d:55002)****[8]**B. C. Eaves,*Homotopies for the continuation of fixed points*, Math. Programming**3**(1972), 1-22. MR**0303953 (46:3089)****[9]**-,*A short course in solving equations with*PL*homotopies*, Non-linear Programming. SIAM-AMS Proceedings, vol. 9, Amer. Math. Soc., Providence, R. I., 1976. MR**0401155 (53:4984)****[10]**B. C. Eaves and H. Scarf,*The solution of systems of piecewise linear equations*, Math. Operations Research**1**(1976), 1-27. MR**0445792 (56:4126)****[11]**S. Friedland,*On inverse multiplicative eigenvalue problems for matrices*, Linear Algebra and Appl.**12**(1975), 127-137. MR**0432672 (55:5658)****[12]**V. Guillemin and A. Pollack,*Differential topology*, Prentice-Hall, Engelwood Cliffs, N. J., 1974. MR**0348781 (50:1276)****[13]**M. Hirsch,*A proof of the non-retractibility of a cell onto its boundary*, Proc. Amer. Math. Soc.**14**(1963), 364-365. MR**0145502 (26:3033)****[14]**-,*Differential topology*, Springer-Verlag, New York, 1976. MR**0448362 (56:6669)****[15]**D. Husemoller,*Fiber bundles*, Springer-Verlag, New York, 1974.**[16]**R. B. Kellogg, T. Y. Li and J. A. Yorke,*A method of continuation for calculating a Brouwer fixed point*, Fixed Points, Algorithms, and Applications (S. Karemdian, ed.), Academic Press, New York, 1977.**[17]**-,*A constructive proof of the Brouwer fixed point theorem and computational results*, SIAM J. Numer. Anal.**13**(1976), 473-483. MR**0416010 (54:4087)****[18]**H. B. Keller,*Numerical solution of bifurcation and non-linear eigenvalue problems*, Applications of Bifurcation Theory, Academic Press, New York (to appear). MR**0455353 (56:13592)****[19]**H. W. Kuhn,*Simplicial approximation of fixed points*, Proc. Nat. Acad. Sci. U. S. A.**61**(1968), 1238-1242. MR**0488010 (58:7589)****[20]**T. Y. Li,*A rigorous algorithm for fixed point computation*(to appear).**[21]**T. Y. Li and J. A. Yorke,*A rigorous algorithm for solving equations when existence is proved using topological degree*(in preparation).**[22]**Y.-C. Lu,*Singularity theory and an introduction to catastrophe theory*, Springer-Verlag, New York, 1976. MR**0461562 (57:1547)****[23]**G. Meyer,*On solving nonlinear equations with a one-parameter operator embedding*, SIAM J. Numer. Anal.**5**(1968), 739-752. MR**0242366 (39:3697)****[24]**J. W. Milnor,*Topology from the differential viewpoint*, Univ. of Virginia Press, Charlottesville, Va., 1965. MR**0226651 (37:2239)****[25]**-,*Morse theory*, Ann. of Math. Studies, no. 51, Princeton Univ. Press, Princeton, N. J., 1963.**[26]**L. Nirenberg,*Topics in nonlinear functional analysis*, New York Univ. Lecture Notes, 1974. MR**0488102 (58:7672)****[27]**P. Rabinowitz,*Some global results for non-linear eigenvalue problems*, J. Functional Analysis**7**(1971), 487-573. MR**0301587 (46:745)****[28]**W. C. Rheinboldt,*Numerical continuation methods for finite element applications*, Formulation and Computational Algorithms in Finite Element Analysis, M.I.T. Press, Cambridge, 1977. MR**0474782 (57:14415)****[29]**R. Saigal,*Fixed point computing methods*, Encyclopedia of Computer Science and Technology, Dekker, New York (to appear).**[30]**-,*On the convergence rate of algorithms for solving equations that are based on methods of complementary pivoting*, Math. Operations Research (to appear).**[31]**H. Scarf,*The approximation of fixed points of a continuous mapping*, SIAM J. Appl. Math.**15**(1967), 1328-1343. MR**0242483 (39:3814)****[32]**S. Smale,*Convergent process of price adjustment and global Newton methods*, J. Math. Econom.**3**(1976), 1-14. MR**0452565 (56:10844)**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
55C20,
58C99,
65H10

Retrieve articles in all journals with MSC: 55C20, 58C99, 65H10

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1978-0478138-5

Keywords:
Homotopy continuation method,
Newton method,
generic approximation,
generic proofs,
fixed points,
bifurcation,
vector fields,
Borsuk-Ulam Theorem

Article copyright:
© Copyright 1978
American Mathematical Society