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

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****[2]**J. C. Alexander,*Bifurcation of zeroes of parametrized functions*, J. Funct. Anal.**29**(1978), no. 1, 37–53. MR**499933**, 10.1016/0022-1236(78)90045-9**[3]**J. C. Alexander,*The additive inverse eigenvalue problem and topological degree*, Proc. Amer. Math. Soc.**70**(1978), no. 1, 5–7. MR**487546**, 10.1090/S0002-9939-1978-0487546-3**[4]**J. C. Alexander and James A. Yorke,*Global bifurcations of periodic orbits*, Amer. J. Math.**100**(1978), no. 2, 263–292. MR**0474406****[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]**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**, 10.1090/S0025-5718-1978-0492046-9**[8]**B. Curtis Eaves,*Homotopies for computation of fixed points*, Math. Programming**3**(1972), 1–22. MR**0303953****[9]**B. Curtis Eaves,*A short course in solving equations with PL homotopies*, Nonlinear programming (Proc. SIAM-AMS Sympos., NewYork, 1975) Amer. Math. Soc., Providence, R. I., 1976, pp. 73–143. SIAM-AMS Proc., Vol. IX. MR**0401155****[10]**B. Curtis Eaves and Herbert Scarf,*The solution of systems of piecewise linear equations*, Math. Oper. Res.**1**(1976), no. 1, 1–27. MR**0445792****[11]**Shmuel Friedland,*On inverse multiplicative eigenvalue problems for matrices*, Linear Algebra and Appl.**12**(1975), no. 2, 127–137. MR**0432672****[12]**Victor Guillemin and Alan Pollack,*Differential topology*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. MR**0348781****[13]**Morris W. Hirsch,*A proof of the nonretractibility of a cell onto its boundary*, Proc. Amer. Math. Soc.**14**(1963), 364–365. MR**0145502**, 10.1090/S0002-9939-1963-0145502-8**[14]**Morris W. Hirsch,*Differential topology*, Springer-Verlag, New York-Heidelberg, 1976. Graduate Texts in Mathematics, No. 33. MR**0448362****[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]**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**0416010****[18]**Herbert B. Keller,*Numerical solution of bifurcation and nonlinear eigenvalue problems*, Applications of bifurcation theory (Proc. Advanced Sem., Univ. Wisconsin, Madison, Wis., 1976) Academic Press, New York, 1977, pp. 359–384. Publ. Math. Res. Center, No. 38. MR**0455353****[19]**Harold W. Kuhn,*Simplicial approximation of fixed points*, Proc. Nat. Acad. Sci. U.S.A.**61**(1968), 1238–1242. MR**0488010****[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]**Yung Chen Lu,*Singularity theory and an introduction to catastrophe theory*, Springer-Verlag, New York, 1976. With an introduction by Peter Hilton; Universitext. MR**0461562****[23]**Gunter H. Meyer,*On solving nonlinear equations with a one-parameter operator imbedding.*, SIAM J. Numer. Anal.**5**(1968), 739–752. MR**0242366****[24]**John W. Milnor,*Topology from the differentiable viewpoint*, Based on notes by David W. Weaver, The University Press of Virginia, Charlottesville, Va., 1965. MR**0226651****[25]**-,*Morse theory*, Ann. of Math. Studies, no. 51, Princeton Univ. Press, Princeton, N. J., 1963.**[26]**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****[27]**Paul H. Rabinowitz,*Some global results for nonlinear eigenvalue problems*, J. Functional Analysis**7**(1971), 487–513. MR**0301587****[28]**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****[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]**Herbert Scarf,*The approximation of fixed points of a continuous mapping*, SIAM J. Appl. Math.**15**(1967), 1328–1343. MR**0242483****[32]**Stephen Smale,*Exchange processes with price adjustment*, J. Math. Econom.**3**(1976), no. 3, 211–226. MR**0452565**

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:
http://dx.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