The homotopy continuation method: numerically implementable topological procedures
Authors:
J. C. Alexander and James A. Yorke
Journal:
Trans. Amer. Math. Soc. 242 (1978), 271284
MSC:
Primary 55C20; Secondary 58C99, 65H10
MathSciNet review:
0478138
Fulltext 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 BorsukUlam 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 parametrized functions,
J. Funct. Anal. 29 (1978), no. 1, 37–53. MR 499933
(80j:58023), http://dx.doi.org/10.1016/00221236(78)900459
 [3]
J.
C. Alexander, The additive inverse eigenvalue
problem and topological degree, Proc. Amer.
Math. Soc. 70 (1978), no. 1, 5–7. MR 487546
(80a:55002), http://dx.doi.org/10.1090/S00029939197804875463
 [4]
J.
C. Alexander and James
A. Yorke, Global bifurcations of periodic orbits, Amer. J.
Math. 100 (1978), no. 2, 263–292. 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]
Shui
Nee Chow, John
MalletParet, 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
(80d:55002), http://dx.doi.org/10.1090/S00255718197804920469
 [8]
B.
Curtis Eaves, Homotopies for computation of fixed points,
Math. Programming 3 (1972), 1–22. MR 0303953
(46 #3089)
 [9]
B.
Curtis Eaves, A short course in solving equations with PL
homotopies, Nonlinear programming (Proc. SIAMAMS Sympos., NewYork,
1975) Amer. Math. Soc., Providence, R. I., 1976, pp. 73–143.
SIAMAMS Proc., Vol. IX. MR 0401155
(53 #4984)
 [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
(56 #4126)
 [11]
Shmuel
Friedland, On inverse multiplicative eigenvalue problems for
matrices, Linear Algebra and Appl. 12 (1975),
no. 2, 127–137. MR 0432672
(55 #5658)
 [12]
Victor
Guillemin and Alan
Pollack, Differential topology, PrenticeHall, Inc., Englewood
Cliffs, N.J., 1974. MR 0348781
(50 #1276)
 [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
(26 #3033), http://dx.doi.org/10.1090/S00029939196301455028
 [14]
Morris
W. Hirsch, Differential topology, SpringerVerlag, New
YorkHeidelberg, 1976. Graduate Texts in Mathematics, No. 33. MR 0448362
(56 #6669)
 [15]
D. Husemoller, Fiber bundles, SpringerVerlag, 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 fixedpoint theorem and
computational results, SIAM J. Numer. Anal. 13
(1976), no. 4, 473–483. MR 0416010
(54 #4087)
 [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
(56 #13592)
 [19]
Harold
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]
Yung
Chen Lu, Singularity theory and an introduction to catastrophe
theory, SpringerVerlag, New York, 1976. With an introduction by Peter
Hilton; Universitext. MR 0461562
(57 #1547)
 [23]
Gunter
H. Meyer, On solving nonlinear equations with a oneparameter
operator imbedding., SIAM J. Numer. Anal. 5 (1968),
739–752. MR 0242366
(39 #3697)
 [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
(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, 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
(58 #7672)
 [27]
Paul
H. Rabinowitz, Some global results for nonlinear eigenvalue
problems, J. Functional Analysis 7 (1971),
487–513. MR 0301587
(46 #745)
 [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
(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]
Herbert
Scarf, The approximation of fixed points of a continuous
mapping, SIAM J. Appl. Math. 15 (1967),
1328–1343. MR 0242483
(39 #3814)
 [32]
Stephen
Smale, Exchange processes with price adjustment, J. Math.
Econom. 3 (1976), no. 3, 211–226. MR 0452565
(56 #10844)
 [1]
 J. F. Adams, Vector fields on spheres, Ann. of Math. (2) 75 (1962), 603632. 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. MalletParet 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), 122. MR 0303953 (46:3089)
 [9]
 , A short course in solving equations with PL homotopies, Nonlinear Programming. SIAMAMS 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), 127. MR 0445792 (56:4126)
 [11]
 S. Friedland, On inverse multiplicative eigenvalue problems for matrices, Linear Algebra and Appl. 12 (1975), 127137. MR 0432672 (55:5658)
 [12]
 V. Guillemin and A. Pollack, Differential topology, PrenticeHall, Engelwood Cliffs, N. J., 1974. MR 0348781 (50:1276)
 [13]
 M. Hirsch, A proof of the nonretractibility of a cell onto its boundary, Proc. Amer. Math. Soc. 14 (1963), 364365. MR 0145502 (26:3033)
 [14]
 , Differential topology, SpringerVerlag, New York, 1976. MR 0448362 (56:6669)
 [15]
 D. Husemoller, Fiber bundles, SpringerVerlag, 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), 473483. MR 0416010 (54:4087)
 [18]
 H. B. Keller, Numerical solution of bifurcation and nonlinear 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), 12381242. 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, SpringerVerlag, New York, 1976. MR 0461562 (57:1547)
 [23]
 G. Meyer, On solving nonlinear equations with a oneparameter operator embedding, SIAM J. Numer. Anal. 5 (1968), 739752. 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 nonlinear eigenvalue problems, J. Functional Analysis 7 (1971), 487573. 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), 13281343. MR 0242483 (39:3814)
 [32]
 S. Smale, Convergent process of price adjustment and global Newton methods, J. Math. Econom. 3 (1976), 114. MR 0452565 (56:10844)
Similar Articles
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/S00029947197804781385
PII:
S 00029947(1978)04781385
Keywords:
Homotopy continuation method,
Newton method,
generic approximation,
generic proofs,
fixed points,
bifurcation,
vector fields,
BorsukUlam Theorem
Article copyright:
© Copyright 1978
American Mathematical Society
