On the efficiency of algorithms of analysis. (English) Zbl 0592.65032

Smale, Steve

Bull. Am. Math. Soc., New Ser. 13, 87-121 (1985).

This paper is a kind of report on the author’s preoccupations concerning the computational complexity. As the author declares, it is partly an exposition of recent results and new open problems, but also some new proofs are given here. There are four principal theorems, named A, B, C and D, twelve problems and many other theorems, lemmas and propositions.
We mention the theorem C, which is not proved in the paper: Let \(K_ A\) be the von Neumann-Wilkinson condition number of the matrix A, \(L_ A=\log K_ A\) and L(n) the average (with the Gauss measure) over real \(n\times n\) matrices;
then (i) (E. Kostlan) \[ L(n)\leq 1+(5/2)\log n; \] (ii) (A. Ocneanu) Given any \(\epsilon >0\), there is \(n_ 0\) such that for \(n>n_ 0\), \[ (2/3-\epsilon)\log n\leq L(n). \] Some titles are also relevant: On efficient zero finding (theorem A). On the efficiency of linear programming (th. B). On well-posed linear systems (th. C). On efficient approximation of integrals (th. D). Convergence of Newton’s method. Purely iterative algorithms. What is an algorithm? Questions of precision.

Reviewer: Gh.Marinescu

MSC:

65J05	General theory of numerical analysis in abstract spaces
65-02	Research exposition (monographs, survey articles) pertaining to numerical analysis
65H10	Numerical computation of solutions to systems of equations
65F10	Iterative numerical methods for linear systems
68W99	Algorithms in computer science
68Q25	Analysis of algorithms and problem complexity
90C05	Linear programming
65K05	Numerical mathematical programming methods

Keywords:

computational complexity; von Neumann-Wilkinson condition number; efficient zero finding; efficiency of linear programming; well-posed linear systems; Newton’s method

References:

[1]	Kendall E. Atkinson, An introduction to numerical analysis, John Wiley & Sons, New York-Chichester-Brisbane, 1978. · Zbl 0402.65001
[2]	Béla Barna, Über die Divergenzpunkte des Newtonschen Verfahrens zur Bestimmung von Wurzeln algebraischen Gleichungen. II, Publ. Math. Debrecen 4 (1956), 384 – 397 (German). · Zbl 0073.10603
[3]	Paul Blanchard, Complex analytic dynamics on the Riemann sphere, Bull. Amer. Math. Soc. (N.S.) 11 (1984), no. 1, 85 – 141. · Zbl 0558.58017
[4]	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. · Zbl 0622.68038
[5]	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). · Zbl 0488.90047
[6]	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. · Zbl 0524.65032
[7]	George B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, N.J., 1963. · Zbl 0108.33103
[8]	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. · Zbl 0123.37102
[9]	Adrien Douady, Systèmes dynamiques holomorphes, Bourbaki seminar, Vol. 1982/83, Astérisque, vol. 105, Soc. Math. France, Paris, 1983, pp. 39 – 63 (French). · Zbl 0532.30019
[10]	B. Curtis Eaves and Herbert Scarf, The solution of systems of piecewise linear equations, Math. Oper. Res. 1 (1976), no. 1, 1 – 27. · Zbl 0458.65056
[11]	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.
[12]	P. Fatou, Sur les équations fonctionnelles, Bull. Soc. Math. France 48 (1920), 33 – 94 (French).
[13]	George E. Forsythe and Cleve B. Moler, Computer solution of linear algebraic systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. · Zbl 0154.40401
[14]	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. · Zbl 0402.01005
[15]	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.
[16]	W. K. Hayman, Multivalent functions, Cambridge Tracts in Mathematics and Mathematical Physics, No. 48, Cambridge University Press, Cambridge, 1958. · Zbl 0082.06102
[17]	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. · Zbl 0363.30001
[18]	Einar Hille, Analytic function theory. Vol. II, Introductions to Higher Mathematics, Ginn and Co., Boston, Mass.-New York-Toronto, Ont., 1962. · Zbl 0102.29401
[19]	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. · Zbl 0542.65025
[20]	Hui Hsiung Kuo, Gaussian measures in Banach spaces, Lecture Notes in Mathematics, Vol. 463, Springer-Verlag, Berlin-New York, 1975. · Zbl 0306.28010
[21]	Serge Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. · Zbl 0193.34701
[22]	M. L. Mehta, Random matrices and the statistical theory of energy levels, Academic Press, New York-London, 1967. · Zbl 0925.60011
[23]	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. · Zbl 0304.65002
[24]	H.-O. Peitgen, D. Saupe, and F. von Haeseler, Cayley’s problem and Julia sets, Math. Intelligencer 6 (1984), no. 2, 11 – 20. · Zbl 0549.68101
[25]	James Renegar, On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials, Math. Programming 32 (1985), no. 3, 301 – 318. · Zbl 0577.65039
[26]	James Renegar, On the cost of approximating all roots of a complex polynomial, Math. Programming 32 (1985), no. 3, 319 – 336. · Zbl 0577.65040
[27]	Donald G. Saari and John B. Urenko, Newton’s method, circle maps, and chaotic motion, Amer. Math. Monthly 91 (1984), no. 1, 3 – 17. · Zbl 0532.58016
[28]	Ron Shamir, The efficiency of the simplex method: a survey, Management Sci. 33 (1987), no. 3, 301 – 334. · Zbl 0612.90081
[29]	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. · Zbl 0846.65018
[30]	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. · Zbl 0625.65036
[31]	Steve Smale, The mathematics of time, Springer-Verlag, New York-Berlin, 1980. Essays on dynamical systems, economic processes, and related topics. · Zbl 0451.58001
[32]	Steve Smale, A convergent process of price adjustment and global Newton methods, J. Math. Econom. 3 (1976), no. 2, 107 – 120. · Zbl 0354.90018
[33]	Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1 – 36. · Zbl 0456.12012
[34]	Steve Smale, On the average number of steps of the simplex method of linear programming, Math. Programming 27 (1983), no. 3, 241 – 262. · Zbl 0526.90060
[35]	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.
[36]	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.
[37]	Marshall C. Yovits , Advances in computers. Vol. 23, Advances in Computers, vol. 23, Academic Press, Inc., Orlando, FL, 1984. · Zbl 0613.68006
[38]	J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. · Zbl 0258.65037
[39]	J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. · Zbl 1041.65502