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.
  • Kendall E. Atkinson, An introduction to numerical analysis, John Wiley & Sons, New York-Chichester-Brisbane, 1978. MR 504339
  • Béla Barna, Über die Divergenzpunkte des Newtonschen Verfahrens zur Bestimmung von Wurzeln algebraischen Gleichungen. II, Publ. Math. Debrecen 4 (1956), 384–397 (German). MR 0078956
  • Paul Blanchard, Complex analytic dynamics on the Riemann sphere, Bull. Amer. Math. Soc. (N.S.) 11 (1984), no. 1, 85–141. MR 741725, 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, 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
  • George B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, N.J., 1963. MR 0201189
  • Constructive aspects of the fundamental theorem of algebra, Proceedings of a Symposium Conducted at the IBM Research Laboratory, Zürich-Rüschlikon, June 5-7, vol. 1967, Wiley-Interscience A Division of John Wiley & Sons, Ltd., London-New York-Sydney, 1969. MR 0253555
  • J. Demmel, A numerical analyst's Jordan canonical form, Thesis, Univ. of California, Berkeley, 1983.
  • Robert Dorfman, Paul A. Samuelson, and Robert M. Solow, Linear programming and economic analysis, A Rand Corporation Research Study, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR 0128543
  • 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
  • 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
  • K. D. Elworthy, Gaussian measures on Banach spaces and manifolds, Global analysis and its applications (Lectures, Internat. Sem. Course, Internat. Centre Theoret. Phys., Trieste, 1972) Internat. Atomic Energy Agency, Vienna, 1974, pp. 151–166. MR 0464297
  • P. Fatou, Sur les équations fonctionnelles, Bull. Soc. Math. France 48 (1920), 33–94 (French). MR 1504792
  • George E. Forsythe and Cleve B. Moler, Computer solution of linear algebraic systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223
  • Herman H. Goldstine, A history of numerical analysis from the 16th through the 19th century, Springer-Verlag, New York-Heidelberg, 1977. Studies in the History of Mathematics and Physical Sciences, Vol. 2. MR 0484905
  • John Guckenheimer, Endomorphisms of the Riemann sphere, Global Analysis (Proc. Sympos. Pure Math. Vol, XIV, Berkeley, Calif., 1968), Amer. Math. Soc., Providence, R.I., 1970, pp. 95–123. MR 0274740
  • W. K. Hayman, Multivalent functions, Cambridge Tracts in Mathematics and Mathematical Physics, No. 48, Cambridge University Press, Cambridge, 1958. MR 0108586
  • Peter Henrici, Applied and computational complex analysis. Vol. 2, Wiley Interscience [John Wiley & Sons], New York-London-Sydney, 1977. Special functions—integral transforms—asymptotics—continued fractions. MR 0453984
  • Einar Hille, Analytic function theory. Vol. II, Introductions to Higher Mathematics, Ginn and Co., Boston, Mass.-New York-Toronto, Ont., 1962. MR 0201608
  • 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, 10.1007/BF02612355
  • Hui Hsiung Kuo, Gaussian measures in Banach spaces, Lecture Notes in Mathematics, Vol. 463, Springer-Verlag, Berlin-New York, 1975. MR 0461643
  • Serge Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR 0197234
  • C. Martin and R. Hurley, Newton's algorithm and chaotic dynamical systems, SIAM J. Math. Anal. 16 (1984), 238-252.
  • M. L. Mehta, Random matrices and the statistical theory of energy levels, Academic Press, New York-London, 1967. MR 0220494
  • A. Ocneanu, On the stability of large linear systems (to appear).
  • A. M. Ostrowski, Solution of equations in Euclidean and Banach spaces, Academic Press [A Subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Third edition of Solution of equations and systems of equations; Pure and Applied Mathematics, Vol. 9. MR 0359306
  • 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, 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, 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, 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, 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, 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, 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, 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
  • Steve Smale, A convergent process of price adjustment and global Newton methods, J. Math. Econom. 3 (1976), no. 2, 107–120. MR 0411577
  • Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1–36. MR 590817, 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, 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. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
  • J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456

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