Some basic information on information-based complexity theory
From MaRDI portal
error analysisinformation-based complexityapproximate solutions to mathematical problemsoptimal solution of large eigenpair problemsoptimal solution of large linear systems
Complexity and performance of numerical algorithms (65Y20) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Analysis of algorithms and problem complexity (68Q25) Iterative numerical methods for linear systems (65F10)
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 , the class of admissible problem instances. By overlooking '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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3827201 (Why is no real title available?)
- scientific article; zbMATH DE number 3917549 (Why is no real title available?)
- scientific article; zbMATH DE number 3671573 (Why is no real title available?)
- scientific article; zbMATH DE number 3688713 (Why is no real title available?)
- scientific article; zbMATH DE number 3787936 (Why is no real title available?)
- scientific article; zbMATH DE number 193625 (Why is no real title available?)
- scientific article; zbMATH DE number 3553634 (Why is no real title available?)
- scientific article; zbMATH DE number 3628385 (Why is no real title available?)
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- A survey of information-based complexity
- Estimates for Some Computational Techniques in Linear Algebra
- Estimating the Largest Eigenvalue of a Positive Definite Matrix
- Fast multiplication of large numbers
- Gaussian elimination is not optimal
- How to Make the Lanczos Algorithm Converge Slowly
- Information-based numerical practice
- On Estimating the Largest Eigenvalue with the Lanczos Algorithm
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On the Optimal Solution of Large Linear Systems
- On the Rates of Convergence of the Lanczos and the Block-Lanczos Methods
- On the number of multiplications necessary to compute certain functions
- Recent developments in information-based complexity
- The Conjugate Gradient Method for Linear and Nonlinear Operator Equations
- The Software Scene in the Extraction of Eigenvalues from Sparse Matrices
- The use of a refined error bound when updating eigenvalues of tridiagonals
- Über eine Verallgemeinerung einer Ungleichung von L.V. Kantorowitsch
Cited in
(4)
This page was built for publication: Some basic information on information-based complexity theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3992023)
