Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



Some basic information on information-based complexity theory

Author: Beresford N. Parlett
Journal: Bull. Amer. Math. Soc. 26 (1992), 3-27
MSC (2000): Primary 68Q30; Secondary 65Y20
MathSciNet review: 1102755
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Numerical analysts might be expected to pay close attention to a branch of complexity theory called information-based complexity theory (IBCT), which produces an abundance of impressive results about the quest for approximate solutions to mathematical problems. Why then do most numerical analysts turn a cold shoulder to IBCT? Close analysis of two representative papers reveals a mixture of nice new observations, error bounds repackaged in new language, misdirected examples, and misleading theorems.

Some elements in the framework of IBCT, erected to support a rigorous yet flexible theory, make it difficult to judge whether a model is off-target or reasonably realistic. For instance, a sharp distinction is made between information and algorithms restricted to this information. Yet the information itself usually comes from an algorithm, so the distinction clouds the issues and can lead to true but misleading inferences. Another troublesome aspect of IBCT is a free parameter F, the class of admissible problem instances. By overlooking F's membership fee, the theory sometimes distorts the economics of problem solving in a way reminiscent of agricultural subsidies.

The current theory's surprising results pertain only to unnatural situations, and its genuinely new insights might serve us better if expressed in the conventional modes of error analysis and approximation theory.

References [Enhancements On Off] (What's this?)

  • [Ba, 1987] I. Babuska, Information-based numerical practice, J. Complexity 3 (1987), 331-346. MR 919680 (89f:65056)
  • [Bl, Shu, & Sm, 1989] L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers; NP completeness, recursive functions, and Turing machines, Bull. Amer. Math. Soc. (N.S.) 21 (1989), 1-46. MR 974426 (90a:68022)
  • [Bo & Mu, 1975] A. Borodin and I. Munro, Computational complexity of algebraic and numeric problems, Amer. Elsevier, New York, 1975. MR 0468309 (57:8145)
  • [Cu & Wi, 1985] J. K. Cullum and R. A. Willoughby, Lanczos algorithms for large symmetric eigenvalue computations, Vol. I: Theory, Progr. Comput. Sci., Birkhauser, Basel, 1985. MR 808962 (87h:65064a)
  • [Da, 1967] J. W. Daniel, The conjugate gradient method for linear and nonlinear operator equations, SIAM J. Numer. Anal. 4 (1967), 10-26. MR 0217987 (36:1076)
  • [Go & Va, 1984] G. H. Golub and C. V. Van Loan, Advanced matrix computations, Johns Hopkins Univ. Press, Maryland, 1984.
  • [Je, 1977] A. Jennings, Matrix computation for engineers and scientists, John Wiley & Sons, Chichester, 1977. MR 0471244 (57:10981)
  • [Ka, 1966] S. Kaniel, Estimates for some computational techniques in linear algebra, Math. Comp. 20 (1966), 369-378. MR 0234618 (38:2934)
  • [Ku, 1986] J. Kuczynski, A generalized minimal residual algorithm for finding an eigenpair of a large matrix, J. Complexity 2 (1986), 131-162.
  • [Ku, 1985] -, Implementation of the GMR algorithm for large symmetric eigenproblems, Tech. Report, Comp. Sci. Dept., Columbia University, New York, 1985.
  • [Ku & Wo, 1992] J. Kuczynski and H. Woźniakowski, Average case complexity of the symmetric Lanczos algorithm, SIAM J. Matrix Anal. Appl., 1992 (to appear).
  • [La, 1952] C. Lanczos, Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bur. Standards 49 (1952), 33-51. MR 0051583 (14:501g)
  • [Me, 1963] G. Meinardus, Über eine Verallgemeinerung einer Ungleichung von L. V. Kantorowitsch, Numer. Math. 5 (1963), 14-23. MR 0160311 (28:3525)
  • [O'L, Ste & Va, 1979] D. O'Leary, G. W. Stewart and J. S. Vandergraft, Estimating the largest eigenvalue of a positive definite matrix, Math. Comp. 33 (1979), 1289-1292. MR 537973 (80d:65048)
  • [Pa, 1980] B. N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, New Jersey, 1980. MR 570116 (81j:65063)
  • [Pa, 1982] -, Two monitoring schemes for the Lanczos algorithm, Computing Methods in Applied Sciences and Engineering (V. R. Glowinski and J. L. Lions, eds.), North-Holland Press, 1982.
  • [Pa, 1984] -, The software scene in the extraction of eigenvalues from sparse matrices, SIAM J. Sci. Statist. Comput. 5 (1984), 590-603. MR 754487 (85i:65048)
  • [Pa & No, 1985] B. N. Parlett and B. Nour-Omid, The use of refined error bounds when updating eigenvalues of tridiagonals, Linear Algebra Appl. 68 (1985), 179-219. MR 794821 (86j:65046)
  • [Pa, Si & Str, 1982] B. N. Parlett, H. A. Simon, and L. M. Stringer, On estimating the largest eigenvalue with the Lanczos algorithm, Math. Comp. 38 (1982), 153-165. MR 637293 (82m:65033)
  • [Pac, 1986] E. Packel, Review of A general theory of optimal algorithms, by J. F. Traub and H. Woźniakowski (Academic Press, New York, 1980), SIAM Rev. 28 (1986), 435-437. MR 584446 (84m:68041)
  • [Pac & Wo, 1987] E. Packel and H. Woźniakowski, Recent developments on information-based complexity, Bull. Amer. Math. Soc. (N.S.) 17 (1987), 9-26. MR 888879 (88h:65006)
  • [Ra, 1972] M. O. Rabin, Solving linear equations by means of scalar products, Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, eds.), Plenum Press, New York, 1972, pp. 11-20. MR 0391584 (52:12405)
  • [Sa, 1980] Y. Saad, On the rates of convergence of the Lanczos and the block-Lanczos methods, SIAM J. Numer. Anal. 17 (1980), 687-706. MR 588755 (82g:65022)
  • [Sc, 1979] D. S. Scott, How to make the Lanczos algorithm converge slowly, Math. Comp. 33 (1979), 239-247. MR 514821 (80c:65091)
  • [Sch & Str, 1971] A. Schoenhage and V. Strassen, Schnelle Multiplikation Grosser Zahlen, Commuting 7 (1971), 281-292. MR 0292344 (45:1431)
  • [Sh, 1977] I. Shavitt, The method of configuration interaction, Modern Theoretical Chemistry, vol. 3 (H. P. Schaefer, ed.), Plenum Press, 1977.
  • [Shu, 1987] M. Shub, Review of Information, uncertainty, complexity by J. F. Traub, H. Woźniakowski et al. (Addison-Wesley, Reading, MA 1983), SIAM Rev. 29 (1987), 495-496.
  • [Sti, 1958] E. Stiefel, Kernel polynomials in linear algebra and their numerical applications, NBS Appl. Math. 43 (1958), 1-22. MR 0092214 (19:1080c)
  • [Str, 1969] V. Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354-356. MR 0248973 (40:2223)
  • [Tr & Wo, 1980] J. F. Traub and H. Woźniakowski, A general theory of optimal algorithms, Academic Press, New York, 1980. MR 584446 (84m:68041)
  • [Tr & Wo, 1984] -, On the optimal solution of large linear systems, J. Assoc. Comput. Mach., 31 (1984), 545-559. MR 819157
  • [Tr & Wo, 1988] -, Information-based complexity, Academic Press, New York, 1988. MR 958691 (90f:68085)
  • [Tr, Wo & Wa, 1983] J. F. Traub, H. Woźniakowski, and G. Wasilkowski, Information, uncertainty, complexity, Addison-Wesley, Reading, 1983.
  • [Wi, 1970] S. Winograd, On the number of multiplication necessary to compute certain functions, Comm. Pure. Appl. Math. 23 (1970), 165-179. MR 0260150 (41:4778)
  • [Wi, 1980] -, Arithmetic complexity of computations, CBMS-NSF Regional Conf. Ser. In Appl. Math., vol. 33, SIAM, Philadelphia, 1980 MR 565260 (81k:68039)
  • [Wo, 1985] H. Woźniakowski, A survey of information-based complexity, J. Complexity 1 (1985), 11-44. MR 829868 (87d:68050)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 68Q30, 65Y20

Retrieve articles in all journals with MSC (2000): 68Q30, 65Y20

Additional Information

Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society