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
DOI: https://doi.org/10.1090/S0273-0979-1985-15391-1
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.
  • Kendall E. Atkinson, An introduction to numerical analysis, John Wiley & Sons, New York-Chichester-Brisbane, 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
  • Paul Blanchard, Complex analytic dynamics on the Riemann sphere, Bull. Amer. Math. Soc. (N.S.) 11 (1984), no. 1, 85–141. MR 741725, https://doi.org/10.1090/S0273-0979-1984-15240-6
  • Lenore Blum and Michael Shub, Evaluating rational functions: infinite precision is finite cost and tractable on average, SIAM J. Comput. 15 (1986), no. 2, 384–398. MR 837590, https://doi.org/10.1137/0215026
  • K.-H. Borgwardt, The average number of pivot steps required by the simplex-method is polynomial, Z. Oper. Res. Ser. A-B 26 (1982), no. 5, A157–A177 (English, with German summary). MR 686603
  • J. Curry, On the periodic behaviour of Newton's Method for a family of real cubic polynomials, preprint, 1983.
  • James H. Curry, Lucy Garnett, and Dennis Sullivan, On the iteration of a rational function: computer experiments with Newton’s method, Comm. Math. Phys. 91 (1983), no. 2, 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
  • Adrien Douady, Systèmes dynamiques holomorphes, Bourbaki seminar, Vol. 1982/83, Astérisque, vol. 105, Soc. Math. France, Paris, 1983, pp. 39–63 (French). 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 équations fonctionnelles, Bull. Soc. Math. France 48 (1920), 33–94 (French). 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.
  • Harold W. Kuhn, Ze Ke Wang, and Sen Lin Xu, On the cost of computing roots of polynomials, Math. Programming 28 (1984), no. 2, 156–163. MR 733207, https://doi.org/10.1007/BF02612355
  • 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. von Haeseler, Cayley’s problem and Julia sets, Math. Intelligencer 6 (1984), no. 2, 11–20. MR 738904, https://doi.org/10.1007/BF03024150
  • James Renegar, On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials, Math. Programming 32 (1985), no. 3, 301–318. MR 796428, https://doi.org/10.1007/BF01582051
  • James Renegar, On the cost of approximating all roots of a complex polynomial, Math. Programming 32 (1985), no. 3, 319–336. MR 796429, https://doi.org/10.1007/BF01582052
  • 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.
  • Donald G. Saari and John B. Urenko, Newton’s method, circle maps, and chaotic motion, Amer. Math. Monthly 91 (1984), no. 1, 3–17. MR 729188, https://doi.org/10.2307/2322163
  • G. Saunders, Iteration of rational functions of one complex variable and basins of attractive fixed points, Thesis, Univ. of California, Berkeley, 1984.
  • Ron Shamir, The efficiency of the simplex method: a survey, Management Sci. 33 (1987), no. 3, 301–334. MR 885847, https://doi.org/10.1287/mnsc.33.3.301
  • 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.
  • Michael Shub and Steve Smale, Complexity of Bezout’s theorem. III. Condition number and packing, J. Complexity 9 (1993), no. 1, 4–14. Festschrift for Joseph F. Traub, Part I. MR 1213484, https://doi.org/10.1006/jcom.1993.1002
  • M. Shub and S. Smale, Computational complexity: on the geometry of polynomials and a theory of cost. II, SIAM J. Comput. 15 (1986), no. 1, 145–161. MR 822199, https://doi.org/10.1137/0215011
  • Steve Smale, The mathematics of time, Springer-Verlag, New York-Berlin, 1980. Essays on dynamical systems, economic processes, and related topics. MR 607330
  • S. Smale II, A convergent process of price adjustment and global Newton methods, J. Math. Econom. 3 (1976), 107-120. MR 411577
  • Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1–36. MR 590817, https://doi.org/10.1090/S0273-0979-1981-14858-8
  • Steve Smale, On the average number of steps of the simplex method of linear programming, Math. Programming 27 (1983), no. 3, 241–262. MR 725621, https://doi.org/10.1007/BF02591902
  • S. Smale, The problem of the average speed of the simplex method, Mathematical programming: the state of the art (Bonn, 1982) Springer, Berlin, 1983, pp. 530–539. MR 717413
  • Dennis Sullivan, Quasiconformal homeomorphisms in dynamics, topology, and geometry, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986) Amer. Math. Soc., Providence, RI, 1987, pp. 1216–1228. 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.
  • Marshall C. Yovits (ed.), Advances in computers. Vol. 23, Advances in Computers, vol. 23, Academic Press, Inc., Orlando, FL, 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

DOI: https://doi.org/10.1090/S0273-0979-1985-15391-1

American Mathematical Society