Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-25T00:25:06.628Z Has data issue: false hasContentIssue false
  • English
  • Français

Complexity theory and numerical analysis

Published online by Cambridge University Press:  07 November 2008

Steve Smale
Steve Smale
Affiliation:
Department of MathematicsCity University of Hong KongHong Kong E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

Complexity theory of numerical analysis is the study of the number of arithmetic operations required to pass from the input to the output of a numerical problem.

Type
Research Article
Information
Acta Numerica , Volume 6 , January 1997 , pp. 523 - 551
Copyright
Copyright © Cambridge University Press 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Allgower, E. and Georg, K. (1990), Numerical Continuous Methods, Springer.CrossRefGoogle Scholar
Allgower, E. and Georg, K. (1993), Continuation and path following, in Acta Numerica, Vol. 2, Cambridge University Press, pp. 1–64.Google Scholar
Axelsson, O. (1994), Iterative Solution Methods, Cambridge University Press.CrossRefGoogle Scholar
Batterson, S. (1994), ‘Convergence of the Francis shifted QR algorithm on normal matrices’, Linear Algebra Appl. 207, 181–195.CrossRefGoogle Scholar
Batterson, S. and Day, D. (1992), ‘Linear convergence in the shifted QR algorithm’, Math. Comp. 59, 141–151.Google Scholar
Batterson, S. and Smillie, J. (1989), ‘The dynamics of Rayleigh quotient iteration’, SIAM J. Numer. Anal. 26, 624–636.CrossRefGoogle Scholar
Batterson, S. and Smillie, J. (1990), ‘Rayleigh quotient iteration for nonsymmetric matrices’, Math. Comp. 55, 169–178.CrossRefGoogle Scholar
Ben-Or, M. (1983), Lower bounds for algebraic computation trees, in 15th Annual ACM Symposium on the Theory of Computing, pp. 80–86.Google Scholar
Bini, D. and Pan, V. (1987), ‘Sequential and parallel complexity of approximating polynomial zeros’, Computers and Mathematics (with applications) 14, 591–622.Google Scholar
Bini, D. and Pan, V. (1994), Polynomial and Matrix Computations, Birkhäuser, Basel.CrossRefGoogle Scholar
Blum, L., Cucker, F., Shub, M. and Smale, S. (1996), ‘Complexity and real computation: a manifesto’, Int. J. Bifurcation and Chaos 6, 3–26. Referred to as the Manifesto.CrossRefGoogle Scholar
Blum, L., Cucker, F., Shub, M. and Smale, S. (1997), Complexity and Real Computation, Springer. To appear. Referred to as BCSS (1997).Google Scholar
Blum, L., Shub, M. and Smale, S. (1989), ‘On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines’, Bull. Amer. Math. Soc. 21, 1–46. Referred to as BSS (1989).CrossRefGoogle Scholar
Brockett, R. (1973), in Geometric Methods in Systems Theory, Proceedings of the NATO Advanced Study Institute (Mayne, D. and Brockett, R., eds), D. Reidel, Dordrecht.Google Scholar
Brownawell, W. (1987), ‘Bounds for the degrees in the Nullstellensatz’, Annals of Math. 126, 577–591.CrossRefGoogle Scholar
Collins, G. (1975), Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition, Vol. 33 of Lect. Notes in Comp. Sci., Springer, pp. 134–183.Google Scholar
Cuppen, J. J. M. (1981), ‘A divide and conquer method for the symmetric tridiagonal eigenproblem’, Numer. Math. 36, 177–195.CrossRefGoogle Scholar
Dedieu, J.-P. (1997 a), Approximate solutions of numerical problems, condition number analysis and condition number theorems, in Proceedings of the Summer Seminar on ‘Mathematics of Numerical Analysis: Real Number Algorithms’, AMS Lectures in Applied Mathematics (Renegar, J., Shub, M. and Smale, S., eds), AMS, Providence, RI. To appear.Google Scholar
Dedieu, J.-P. (1997 b), Condition number analysis for sparse polynomial systems. Preprint.CrossRefGoogle Scholar
Dedieu, J.-P. (1997 c), ‘Condition operators, condition numbers and condition number theorem for the generalized eigenvalue problem’, Linear Algebra Appl. To appear.CrossRefGoogle Scholar
Dedieu, J.-P. (1997 d), ‘Estimations for separation number of a polynomial system’, J. Symbolic Computation. To appear.CrossRefGoogle Scholar
Dégot, J. and Beauzamy, B. (1997), ‘Differential identities’, Trans. Amer. Math. Soc. To appear.Google Scholar
Dejon, B. and Henrici, P. (1969), Constructive Aspects of the Fundamental Theorem of Algebra, Wiley.Google Scholar
Demmel, J. (1987), ‘On condition numbers and the distance to the nearest ill-posed problem’, Numer. Math. 51, 251–289.CrossRefGoogle Scholar
Dongarra, J. J. and Sorensen, D. C. (1987), ‘A fully parallel algorithm for the symmetric eigenvalue problem’, SIAM J. Sci. Statist. Comput. 8, 139–154.CrossRefGoogle Scholar
Du, Q., Jin, M., Li, T. Y. and Zeng, Z. (1997 a), ‘The quasi-Laguerre iteration’, Math. Comp. To appear.CrossRefGoogle Scholar
Du, Q., Jin, M., Li, T. Y. and Zeng, Z. (1997 b), ‘Quasi-Laguerre iteration in solving symmetric tridiagonal eigenvalue problems’, SIAM J. Sci. Comput. To appear.Google Scholar
Eckart, C. and Young, G. (1936), ‘The approximation of one matrix by another of lower rank’, Psychometrika 1, 211–218.CrossRefGoogle Scholar
Edelman, A. (1988), ‘Eigenvalues and condition numbers of random matrices’, SIAM J. Matrix Anal. Appl. 9, 543–556.CrossRefGoogle Scholar
Edelman, A. and Kostlan, E. (1995), ‘How many zeros of a random polynomial are real?’, Bull. Amer. Math. Soc. 32, 1–38.CrossRefGoogle Scholar
Gauss, C. F. (1973), Werke, Band X, Georg Olms, New York.Google Scholar
Giusti, M., Heintz, J., Morais, J. E., Morgenstern, J. and Pardo, L. M. (1997), ‘Straight-line program in geometric elimination theory’, Journal of Pure and Applied Algebra. To appear.Google Scholar
Golub, G. and van Loan, C. (1989), Matrix Computations, Johns Hopkins University Press.Google Scholar
Grigoriev, D. (1987), in Computational complexity in polynomial algebra, Proceedings of the International Congress Math. (Berkeley, 1986), Vol. 1, 2, AMS, Providence, RI, pp. 1452–1460.Google Scholar
Henrici, P. (1977), Applied and Computational Complex Analysis, Wiley.Google Scholar
Hestenes, M. R. and Stiefel, E. (1952), ‘Method of conjugate gradients for solving linear systems’, J. Res. Nat. Bur. Standards 49, 409–436.CrossRefGoogle Scholar
Hirsch, M. and Smale, S. (1979), ‘On algorithms for solving f(x) = 0’, Comm. Pure Appl. Math. 32, 281–312.CrossRefGoogle Scholar
Hoffman, W. and Parlett, B. N. (1978), ‘A new proof of global convergence for the tridiagonal QL algorithm’, SIAM J. Numer. Anal. 15, 929–937.CrossRefGoogle Scholar
Isaacson, E. and Keller, H. (1966), Analysis of Numerical Methods, Wiley, New York.Google Scholar
Keller, H. (1978), Global homotopic and Newton methods, in Recent Advances in Numerical Analysis, Academic Press, pp. 73–94.CrossRefGoogle Scholar
Kellog, R., Li, T. and Yorke, J. (1976), ‘A constructive proof of Brouwer fixed-point theorem and computational results’, SIAM J. Numer. Anal. 13, 473–483.CrossRefGoogle Scholar
Kim, M. (1988), ‘On approximate zeros and rootfinding algorithms for a complex polynomial’, Math. Comp. 51, 707–719.Google Scholar
Kostlan, E. (1988), ‘Complexity theory of numerical linear algebra’, J. Comput. Appl. Math. 22, 219–230.CrossRefGoogle Scholar
Kostlan, E. (1991), ‘Statistical complexity of dominant eigenvector calculation’, J. Complexity 7, 371–379.CrossRefGoogle Scholar
Kostlan, E. (1993), On the distribution of the roots of random polynomials, in From Topology to Computation: Proceedings of the Smalefest (Hirsch, M., Marsden, J. and Shub, M., eds), Springer, pp. 419–431.CrossRefGoogle Scholar
Malajovich, G. (1994), ‘On generalized Newton algorithms: quadratic convergence, path-following and error analysis’, Theoret. Comput. Sci. 133, 65–84.CrossRefGoogle Scholar
Malajovich-Munoz, G. (1993), On the complexity of path-following Newton algorithms for solving polynomial equations with integer coefficients, PhD thesis, University of California at Berkeley.Google Scholar
McNamee, J. M. (1993), ‘A bibliography on roots of polynomials’, J. Comput. Appl. Math. 47(3), 391–394.CrossRefGoogle Scholar
Milnor, J. (1964), On the Betti numbers of real varieties, in Proceedings of the Amer. Math. Soc., Vol. 15, pp. 275–280.CrossRefGoogle Scholar
Neff, C. (1994), ‘Specified precision root isolation is in NC, J. Comput. System Sci. 48, 429–463.CrossRefGoogle Scholar
Neff, C. and Reif, J. (1996), ‘An efficient algorithm for the complex roots problem’, J. Complexity 12, 81–115.CrossRefGoogle Scholar
Oleinik, O. (1951), ‘Estimates of the Betti numbers of real algebraic hypersurfaces’, Mat. Sbornik (N.S.) 28, 635–640. In Russian.Google Scholar
Oleinik, O. and Petrovski, I. (1949), ‘On the topology of real algebraic surfaces’, Izv. Akad. Nauk SSSR 13, 389–402. In Russian; English translation in Transl. Amer. Math. Soc. 1, 399–417 (1962).Google Scholar
Ostrowski, A. (1958), ‘On the convergence of Rayleigh quotient iteration for the computation of the characteristic roots and vectors, I’, Arch. Rational Mech. Anal. 1, 233–241.CrossRefGoogle Scholar
Pan, V. (1997), ‘Solving a polynomial equation: some history and recent progress’, SIAM Review. To appear.CrossRefGoogle Scholar
Parlett, B. N. and Kahan, W. (1969), ‘On the convergence of a practical QR algorithm’, Inform. Process. Lett. 68, 114–118.Google Scholar
Rakhmanov, E. A., Saff, E. B. and Zhou, Y. M. (1994), ‘Minimal discrete energy on the sphere’, Mathematical Research Letters 1, 647–662.CrossRefGoogle Scholar
Rakhmanov, E. A., Saff, E. B. and Zhou, Y. M. (1995), Electrons on the sphere, in Computational Methods and Function Theory (Ali, R. M., Ruscheweyh, S. and Saff, E. B., eds), World Scientific, pp. 111–127.Google Scholar
Renegar, J. (1987 a), ‘On the efficiency of Newton's method in approximating all zeros of systems of complex polynomials’, Math, of Oper. Research 12, 121–148.CrossRefGoogle Scholar
Renegar, J. (1987 b), ‘On the worst case arithmetic complexity of approximating zeros of polynomials’, J. Complexity 3, 90–113.Google Scholar
Renegar, J. (1996), ‘Condition numbers, the Barrier method, and the conjugate gradient method’, SIAM J. Optim. To appear.CrossRefGoogle Scholar
Renegar, J., Shub, M. and Smale, S., eds (1997), Proceedings of the Summer Seminar on ‘Mathematics of Numerical Analysis: Real Number Algorithm’, AMS Lectures in Applied Mathematics, AMS, Providence, RI.Google Scholar
Reznick, B. (1992), Sums of Even Powers of Real Linear Forms, Vol. 463 of Memoirs of the American Mathematical Society, AMS, Providence, RI.Google Scholar
Rice, J. R. (1966), ‘A theory of condition’, SIAM J. Numer. Anal. 3, 287–310.CrossRefGoogle Scholar
Santal, L.ó (1976), Integral Geometry and Geometric Probability, Addison-Wesley, Reading, MA.Google Scholar
Schönhage, A. (1982), The fundamental theorem of algebra in terms of computational complexity, Technical report, Math. Institut der Universitat Tubingen.Google Scholar
Schönhage, A. (1987), Equation solving in terms of computational complexity, in Proceedings of the International Congress of Mathematicans, AMS, Providence, RI.Google Scholar
Shub, M. (1993), On the work of Steve Smale on the theory of computation, in From Topology to Computation: Proceedings of the Smalefest (Hirsch, M., Marsden, J. and Shub, M., eds), Springer, pp. 443–455.CrossRefGoogle Scholar
Shub, M. and Smale, S. (1985), ‘Computational complexity: on the geometry of polynomials and a theory of cost I’, Ann. Sci. École Norm. Sup. 18, 107–142.CrossRefGoogle Scholar
Shub, M. and Smale, S. (1986), ‘Computational complexity: on the geometry of polynomials and a theory of cost II’, SIAM J. Comput. 15, 145–161.CrossRefGoogle Scholar
Shub, M. and Smale, S. (1993 a), ‘Complexity of Bézout's theorem I: geometric aspect’, J. Amer. Math. Soc. 6, 459–501. Referred to as Bez I.Google Scholar
Shub, M. and Smale, S. (1993 b), Complexity of Bézout's theorem II: volumes and probabilities, in Computational Algebraic Geometry (Eyssette, F. and Galligo, A., eds), Vol. 109 of Progress in Mathematics, pp. 267–285. Referred to as Bez II.CrossRefGoogle Scholar
Shub, M. and Smale, S. (1993 c), ‘Complexity of Bézout's theorem III: condition number and packing’, J. Complexity 9, 4–14. Referred to as Bez III.CrossRefGoogle Scholar
Shub, M. and Smale, S. (1994), ‘Complexity of Bézout's theorem V: polynomial time’, Theoret. Comput. Sci. 133, 141–164. Referred to as Bez V.CrossRefGoogle Scholar
Shub, M. and Smale, S. (1996), ‘Complexity of Bézout's theorem IV: probability of success; extensions’, SIAM J. Numer. Anal. 33, 128–148. Referred to as Bez IV.CrossRefGoogle Scholar
Smale, S. (1976), ‘A convergent process of price adjustment and global Newton method’, J. Math. Economy 3, 107–120.Google Scholar
Smale, S. (1981), ‘The fundamental theorem of algebra and complexity theory’, Bull. Amer. Math. Soc. 4, 1–36.CrossRefGoogle Scholar
Smale, S. (1985), ‘On the efficiency of algorithms of analysis’, Bull. Amer. Math. Soc. 13, 87–121.CrossRefGoogle Scholar
Smale, S. (1986), Newton's method estimates from data at one point, in The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics (Ewing, R., Gross, K. and Martin, C., eds), Springer, pp. 185–196.CrossRefGoogle Scholar
Smale, S. (1987 a), Algorithms for solving equations, in Proceedings of the International Congress of Mathematicians, AMS, Providence, RI, pp. 172–195.Google Scholar
Smale, S. (1987b), ‘On the topology of algorithms I’, J. Complexity 3, 81–89.CrossRefGoogle Scholar
Smale, S. (1990), ‘Some remarks on the foundations of numerical analysis’, SIAM Review 32, 211–220.Google Scholar
Steele, J. and Yao, A. (1982), ‘Lower bounds for algebraic decision trees’, Journal of Algorithms 3, 1–8.CrossRefGoogle Scholar
Stein, E. and Weiss, G. (1971), Introduction to Fourier Analysis on Euclidean Spaces, Princeton University Press.Google Scholar
Thom, R. (1965), Sur l'homologie des variétés algébriques réelles, in Differential and Combinatorial Topology (Cairns, S., ed.), Princeton University Press.Google Scholar
Traub, J. and Wozniakowski, H. (1979), ‘Convergence and complexity of Newton iteration for operator equations’, J. Assoc. Comput. Mach. 29, 250–258.CrossRefGoogle Scholar
Traub, J., Wasilkowski, G. and Wozniakowski, H. (1988), Information-Based Complexity, Academic Press.Google Scholar
Trefethen, L. N. (preprint), Why Gaussian elimination is stable for almost all matrices.Google Scholar
Vassiliev, V. A. (1992), Complements of Discriminants of Smooth Maps: Topology and Applications, Vol. 98 of Transl. of Math. Monographs, AMS, Providence, RI. Revised 1994.CrossRefGoogle Scholar
Wang, X. (1993), Some results relevant to Smale's reports, in From Topology to Computation: Proceedings of the Smalefest (Hirsch, M., Marsden, J. and Shub, M., eds), Springer, pp. 456–465.CrossRefGoogle Scholar
Weyl, H. (1932), The Theory of Groups and Quantum Mechanics, Dover.Google Scholar
Wilkinson, J. (1963), Rounding Errors in Algebraic Processes, Prentice-Hall.Google Scholar
Wilkinson, J. (1968), ‘Global convergence of tridiagonal QR algorithm with origin shifts’, Linear Algebra Appl. I, 409–420.CrossRefGoogle Scholar
Wozniakowski, H. (1977), ‘Numerical stability for solving non-linear equations’, Nu-mer. Math. 27, 373–390.CrossRefGoogle Scholar