On the efficiency of algorithms of analysis
HTML articles powered by AMS MathViewer
- by Steve Smale PDF
- Bull. Amer. Math. Soc. 13 (1985), 87-121
References
-
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 78956
- Paul Blanchard, Complex analytic dynamics on the Riemann sphere, Bull. Amer. Math. Soc. (N.S.) 11 (1984), no. 1, 85–141. MR 741725, DOI 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, DOI 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, DOI 10.1007/bf01917108 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
- Bruno Dejon and Peter Henrici (eds.), Constructive aspects of the fundamental theorem of algebra, 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, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. A Rand Corporation Research Study. 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 445792, DOI 10.1287/moor.1.1.1
- 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, Studies in the History of Mathematics and Physical Sciences, Vol. 2, Springer-Verlag, New York-Heidelberg, 1977. 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 Company, 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, DOI 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, Pure and Applied Mathematics, Vol. 9, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Third edition of Solution of equations and systems of equations. 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, DOI 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, DOI 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, DOI 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, DOI 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, DOI 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, DOI 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, DOI 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 411577, DOI 10.1016/0304-4068(76)90019-7
- Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1–36. MR 590817, DOI 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, DOI 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
Additional Information
- 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