Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



On the efficiency of algorithms of analysis

Author: Steve Smale
Journal: Bull. Amer. Math. Soc. 13 (1985), 87-121
MSC (1980): Primary 65-02
MathSciNet review: 799791
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • I. Adler, R. M. Karp and R. Shamir, A simplex variant solving an m x d linear program in O(min (m, Report UCB CSD 83/158, Computer Science Division, University of California, Berkeley (December 1983).
  • I. Adler and W. Megiddo, A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension, Report, Dec. 1983.
  • A. Aho, J. Hopcraft and J. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass., 1979.
  • K. Atkinson, An introduction to numerical analysis, Wiley, N. Y., 1978. MR 504339
  • B. Barna, Über die Divergenzpunkte des Newtonschen Verfahrens zur Bestimmung von Wurzeln Algebraischer Gleichungen. II, Publ. Math. Debrecen 4 (1956), 384-397. MR 78956
  • P. Blanchard, Complex analytic dynamics on the Riemann sphere, Bull. Amer. Math. Soc. (N.S.) 11 (1984), 85-141. MR 741725
  • L. Blum and M. Shub, Evaluating rational functions: Infinite precision is finite cost and tractable on average, SIAM J. Comput. (to appear). MR 837590
  • K. H. Borgwardt, The average number of pivot steps required by the simplex-method is polynomial, Z. Oper. Res. 26 (1982), 157-177. MR 686603
  • J. Curry, On the periodic behaviour of Newton's Method for a family of real cubic polynomials, preprint, 1983.
  • J. Curry, L. Garnett and D. Sullivan, On the iteration of a rational function: Computer experiments with Newton's method, Comm. Math. Phys. 91 (1983), 267-277. MR 723551
  • G. Dantzig, Linear programming and extensions, Princeton Univ. Press, Princeton, N.J., 1963. MR 201189
  • B. Dejon and P. Henrici, Constructive aspects of the fundamental theorem of algebra, Wiley, N. Y., 1969. MR 253555
  • J. Demmel, A numerical analyst's Jordan canonical form, Thesis, Univ. of California, Berkeley, 1983.
  • R. Dorfman, P. Samuelson and R. Solow, Linear programming and economic analysis, McGraw-Hill, N. Y., 1958. MR 128543
  • A. Douady, Systèmes dynamiques holomorphes, Séminaire Bourbaki, No. 599, 1982. MR 728980
  • C. Eaves and H. Scarf, The solution of systems of piecewise linear equations, Math. Oper. Res. 1 (1976), 1-27. MR 445792
  • D. Elworthy, Gaussian measures on Banach spaces and manifolds, Global Analysis and its Applications, Vol. II, International Atomic Energy Agency, Vienna, 1974, pp. 151-166. MR 464297
  • P. Fatou, Sur les equations fonctionnelles, Bull. Soc. Math. France 47, 48 (1919-1920), 161-211; 33-94; 208-314. MR 1504792
  • G. Forsyth and C. Moler, Computer solution of linear algebraic systems, Prentice-Hall, Englewood Cliffs, N. J., 1967. MR 219223
  • H. Goldstine, A history of numerical analysis, from the 16th through the 19th century, Springer-Verlag, Berlin and New York, 1977. MR 484905
  • J. Guckenheimer, Endomorphisms of the Riemann sphere, Global Analysis (Chern and Smale, eds.), Amer. Math. Soc., Providence, R. I., 1970, pp. 95-123. MR 274740
  • W. Hayman, Multivalent functions, Cambridge Univ. Press, Cambridge, 1958. MR 108586
  • P. Henrici, Applied and computational complex analysis, Wiley, N. Y., 1977. MR 453984
  • E. Hille, Analytic function theory. II, Ginn, Boston, 1962. MR 201608
  • G. Julia, Mémoire sur l'itération des fonctions rationnelles, J. Math. Pures Appl. 4 (1918), 47-245.
  • E. Kostlan, Statistical complexity of numerical linear algebra, Thesis, Univ. of Calif. Berkeley, 1985.
  • H. Kuhn, Z. Wang and Senlin Xu, On the cost of computing roots of polynomials, Math. Programming 28 (1984), 156-163. MR 733207
  • H. H. Kuo, Gaussian measures in Banach spaces, Lecture Notes in Math., vol. 463, Springer-Verlag, Berlin and New York, 1975. MR 461643
  • S. Lang, Algebra, Addison-Wesley, Reading, Mass., 1963. MR 197234
  • C. Martin and R. Hurley, Newton's algorithm and chaotic dynamical systems, SIAM J. Math. Anal. 16 (1984), 238-252.
  • M. Mehta, Random matrices and the statistical theory of energy levels, Academic Press, N. Y., 1967. MR 220494
  • A. Ocneanu, On the stability of large linear systems (to appear).
  • A. Ostrowski, Solutions of equations in Euclidean and Banach spaces, Academic Press, N. Y., 1973. MR 359306
  • H. O. Peitgen, D. Saupe and F. v. Haeseler, Cayley's problem and Julia sets, Math. Intelligencer 6 (1984), 11-20. MR 738904
  • J. Renegar I, On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials, Math. Programming (to appear). MR 796428
  • J. Renegar II, On the cost of approximating all roots of a complex polynomial, Math. Programming (to appear). MR 796429
  • J. Renegar III, On the efficiency of Newton's method in approximating all zeros of a system of complex polynomials, preprint, Colorado State Univ., 1984.
  • D. Saari and J. Urenko, Newton's method, circle maps, and chaotic motion, Amer. Math. Monthly 91 (1984), 3-17. MR 729188
  • G. Saunders, Iteration of rational functions of one complex variable and basins of attractive fixed points, Thesis, Univ. of California, Berkeley, 1984.
  • R. Shamir, The efficiency of the simplex method: A survey, preprint, Univ. of California, Berkeley, 1984. MR 885847
  • M. Shub, The geometry and topology of dynamical systems and algorithms for numerical problems, notes prepared for lectures given at D.D.4 Peking University, Beijing, China, Aug.-Sept. 1983.
  • M. Shub and S. Smale I, Computational complexity: On the geometry of polynomials and a theory of cost, Part I, Ann. Sci. École Norm. Sup. (4) (to appear). MR 1213484
  • M. Shub and S. Smale II, Computational complexity: On the geometry of polynomials and a theory of cost: Part II, SIAM J. Computing (to appear). MR 822199
  • S. Smale I, Differentiable dynamical systems, The Mathematics of Time, Springer-Verlag, New York and Berlin, 1980. MR 607330
  • S. Smale II, A convergent process of price adjustment and global Newton methods, J. Math. Econom. 3 (1976), 107-120. MR 411577
  • S. Smale III, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N. S.) 4 (1981), 1-36. MR 590817
  • S. Smale IV, On the average number of steps in the simplex method of linear programming, Math. Programming 27 (1983), 241-262. MR 725621
  • S. Smale V, The problem of the average speed of the Simplex method, Mathematical Programming, The State of the Art (Bonn, 1982) (Bachem et al., eds.), Springer-Verlag, Berlin and New York, 1983. MR 717413
  • D. Sullivan, Quasiconformal homeomorphisms and dynamics III: Topological conjugacy classes of analytic endomorphisms, Ann. of Math, (to appear). MR 934326
  • M. J. Todd, Polynomial expected behavior of a pivoting algorithm for linear complementary and linear programming problems, Technical Report No. 595, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York, 1983.
  • J. Traub and H. Wozniakowski, Information and computation, in Vol. 23, Advances in Computers, vol. 23 (M. C. Yovits, ed.), Academic Press, N. Y., 1984. MR 772573
  • A. Vershik and P. Sporyshev, An estimate of the average number of steps in the simplex method and problems in asymptotic integral geometry, Soviet Math. Dokl. 28 (1983). (Russian)
  • J. Von Neumann, Collected works, vol. V (A. Taub, ed.), MacMillan, N. Y., 1963.
  • J. Wilkinson I, The algebraic eigenvalue problem, Oxford Univ. Press, Oxford, 1965. MR 184422
  • J. Wilkinson II, Rounding errors in algebraic processes, Prentice-Hall, Englewood Cliffs, N. J., 1973. MR 161456

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1980): 65-02

Retrieve articles in all journals with MSC (1980): 65-02

Additional Information


American Mathematical Society