## Some basic information on information-based complexity theory

HTML articles powered by AMS MathViewer

- by Beresford N. Parlett PDF
- Bull. Amer. Math. Soc.
**26**(1992), 3-27 Request permission

## 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

- I. Babuška,
*Information-based numerical practice*, J. Complexity**3**(1987), no. 3, 331–346. MR**919680**, DOI 10.1016/0885-064X(87)90019-7 - Lenore Blum, Mike Shub, and Steve Smale,
*On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines*, Bull. Amer. Math. Soc. (N.S.)**21**(1989), no. 1, 1–46. MR**974426**, DOI 10.1090/S0273-0979-1989-15750-9 - Allan Borodin and Ian Munro,
*The computational complexity of algebraic and numeric problems*, Elsevier Computer Science Library: Theory of Computation Series, No. 1, American Elsevier Publishing Co., Inc., New York-London-Amsterdam, 1975. MR**0468309** - Jane K. Cullum and Ralph A. Willoughby,
*Lánczos algorithms for large symmetric eigenvalue computations. Vol. I*, Progress in Scientific Computing, vol. 3, Birkhäuser Boston, Inc., Boston, MA, 1985. Theory. MR**808962**, DOI 10.1007/978-1-4684-9178-4_{6} - James W. Daniel,
*The conjugate gradient method for linear and nonlinear operator equations*, SIAM J. Numer. Anal.**4**(1967), 10–26. MR**217987**, DOI 10.1137/0704002
G. H. Golub and C. V. Van Loan, - Alan Jennings,
*Matrix computation for engineers and scientists*, Wiley-Interscience [John Wiley & Sons], London-New York-Sydney, 1977. MR**0471244** - Shmuel Kaniel,
*Estimates for some computational techniques in linear algebra*, Math. Comp.**20**(1966), 369–378. MR**234618**, DOI 10.1090/S0025-5718-1966-0234618-4
J. Kuczynski, - Cornelius Lanczos,
*Solution of systems of linear equations by minimized-iterations*, J. Research Nat. Bur. Standards**49**(1952), 33–53. MR**0051583**, DOI 10.6028/jres.049.006 - Günter Meinardus,
*Über eine Verallgemeinerung einer Ungleichung von L. V. Kantorowitsch*, Numer. Math.**5**(1963), 14–23 (German). MR**160311**, DOI 10.1007/BF01385875 - Dianne P. O’Leary, G. W. Stewart, and James S. Vandergraft,
*Estimating the largest eigenvalue of a positive definite matrix*, Math. Comp.**33**(1979), no. 148, 1289–1292. MR**537973**, DOI 10.1090/S0025-5718-1979-0537973-X - Beresford N. Parlett,
*The symmetric eigenvalue problem*, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR**570116**
—, - B. N. Parlett,
*The software scene in the extraction of eigenvalues from sparse matrices*, SIAM J. Sci. Statist. Comput.**5**(1984), no. 3, 590–604. MR**754487**, DOI 10.1137/0905042 - B. N. Parlett and B. Nour-Omid,
*The use of a refined error bound when updating eigenvalues of tridiagonals*, Linear Algebra Appl.**68**(1985), 179–219. MR**794821**, DOI 10.1016/0024-3795(85)90213-7 - B. N. Parlett, H. Simon, and L. M. Stringer,
*On estimating the largest eigenvalue with the Lanczos algorithm*, Math. Comp.**38**(1982), no. 157, 153–165. MR**637293**, DOI 10.1090/S0025-5718-1982-0637293-9 - Joe Fred Traub and H. Woźniakowsi,
*A general theory of optimal algorithms*, ACM Monograph Series, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. MR**584446** - Edward W. Packel and Henryk Woźniakowski,
*Recent developments in information-based complexity*, Bull. Amer. Math. Soc. (N.S.)**17**(1987), no. 1, 9–36. MR**888879**, DOI 10.1090/S0273-0979-1987-15511-X - Michael O. Rabin,
*Solving linear equations by means of scalar products*, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 11–20, 187–212. MR**0391584** - Y. Saad,
*On the rates of convergence of the Lanczos and the block-Lanczos methods*, SIAM J. Numer. Anal.**17**(1980), no. 5, 687–706. MR**588755**, DOI 10.1137/0717059 - D. S. Scott,
*How to make the Lanczos algorithm converge slowly*, Math. Comp.**33**(1979), no. 145, 239–247. MR**514821**, DOI 10.1090/S0025-5718-1979-0514821-5 - A. Schönhage and V. Strassen,
*Schnelle Multiplikation grosser Zahlen*, Computing (Arch. Elektron. Rechnen)**7**(1971), 281–292 (German, with English summary). MR**292344**, DOI 10.1007/bf02242355
I. Shavitt, - Eduard L. Stiefel,
*Kernel polynomials in linear algebra and their numerical applications*, Nat. Bur. Standards Appl. Math. Ser.**49**(1958), 1–22. MR**92214** - Volker Strassen,
*Gaussian elimination is not optimal*, Numer. Math.**13**(1969), 354–356. MR**248973**, DOI 10.1007/BF02165411 - Joe Fred Traub and H. Woźniakowsi,
*A general theory of optimal algorithms*, ACM Monograph Series, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. MR**584446** - J. F. Traub and H. Woźniakowski,
*On the optimal solution of large linear systems*, J. Assoc. Comput. Mach.**31**(1984), no. 3, 545–559. MR**819157**, DOI 10.1145/828.830 - J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski,
*Information-based complexity*, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR**958691**
J. F. Traub, H. Woźniakowski, and G. Wasilkowski, - Shmuel Winograd,
*On the number of multiplications necessary to compute certain functions*, Comm. Pure Appl. Math.**23**(1970), 165–179. MR**260150**, DOI 10.1002/cpa.3160230204 - Shmuel Winograd,
*Arithmetic complexity of computations*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 33, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1980. MR**565260**, DOI 10.1137/1.9781611970364 - H. Woźniakowski,
*A survey of information-based complexity*, J. Complexity**1**(1985), no. 1, 11–44. MR**829868**, DOI 10.1016/0885-064X(85)90020-2

*Advanced matrix computations*, Johns Hopkins Univ. Press, Maryland, 1984.

*A generalized minimal residual algorithm for finding an eigenpair of a large matrix*, J. Complexity

**2**(1986), 131-162. —,

*Implementation of the GMR algorithm for large symmetric eigenproblems*, Tech. Report, Comp. Sci. Dept., Columbia University, New York, 1985. J. Kuczynski and H. Woźniakowski,

*Average case complexity of the symmetric Lanczos algorithm*, SIAM J. Matrix Anal. Appl., 1992 (to appear).

*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.

*The method of configuration interaction*, Modern Theoretical Chemistry, vol. 3 (H. P. Schaefer, ed.), Plenum Press, 1977. 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.

*Information, uncertainty, complexity*, Addison-Wesley, Reading, 1983.

## Additional Information

- © Copyright 1992 American Mathematical Society
- Journal: Bull. Amer. Math. Soc.
**26**(1992), 3-27 - MSC (2000): Primary 68Q30; Secondary 65Y20
- DOI: https://doi.org/10.1090/S0273-0979-1992-00239-2
- MathSciNet review: 1102755