Tractability of multivariate problems. Volume I: Linear information. (English) Zbl 1156.65001

EMS Tracts in Mathematics 6. Zürich: European Mathematical Society (EMS) (ISBN 978-3-03719-026-5/hbk). xi, 384 p. (2008).
This book is a first of three volumes of the authors devoted to the study of the tractability of multivariate problems. The authors present various existing results obtained by many authors during last years, as well as numerous new results.
This volume begins with twelve examples of particular multivariate problems, along with a survey of results in information based complexity that are especially relevant to tractability. This list comprises integration, approximation of \(C^{\infty}\) functions, discrepancy, absolute, relative and normalized errors and Monte Carlo algorithms, among others.
The rest of the volume is devoted to the tractability of algorithms using linear information (arbitrary continuous linear functionals). The tractability results are illustrated for many specific multivariate problems, general linear problems including multivariate integration, approximation, as well as a number of specific non-linear problems such as partial differential and integral equations. The book contains a number of open problems that could be of interest to a general audience of mathematicians, and very long list of 296 references.


65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
65Y20 Complexity and performance of numerical algorithms
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
41A63 Multidimensional problems
46E22 Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces)
28C20 Set functions and measures and integrals in infinite-dimensional spaces (Wiener measure, Gaussian measure, etc.)
46E30 Spaces of measurable functions (\(L^p\)-spaces, Orlicz spaces, Köthe function spaces, Lorentz spaces, rearrangement invariant spaces, ideal spaces, etc.)
65D32 Numerical quadrature and cubature formulas
65C05 Monte Carlo methods
Full Text: DOI