Book Details

Search page | Title Index  | Author Index

Preface | Table of Contents | MARC record  | Metadata XML  | e-Book PDF (4098 KB)
Tractability of Multivariate Problems
EMS Tracts in Mathematics Vol. 12

Erich Novak (University of Jena, Germany)
Henryk Wo┼║niakowski (Columbia University, New York, USA, and University of Warsaw, Poland)

Tractability of Multivariate Problems

Volume II: Standard Information for Functionals

ISBN print 978-3-03719-084-5, ISBN online 978-3-03719-584-0
DOI 10.4171/084
July 2010, 675 pages, hardcover, 17 x 24 cm.
98.00 Euro

This three-volume set is a comprehensive study of the tractability of multivariate problems. The present second volume deals with algorithms using standard information consisting of function values for the approximation of linear and selected nonlinear functionals. An important example is numerical multivariate integration.

The proof techniques used in volumes I and II are quite different. It is especially hard to establish meaningful lower error bounds for the approximation of functionals by using finitely many function values. Here, the concept of decomposable reproducing kernels is helpful, allowing it to find matching lower and upper error bounds for some linear functionals. It is then possible to conclude tractability results from such error bounds.

Tractability results even for linear functionals are very rich in variety. There are infinite-dimensional Hilbert spaces for which the approximation with an arbitrarily small error of all linear functionals requires only one function value. There are Hilbert spaces for which all nontrivial linear functionals suffer from the curse of dimensionality. This holds for unweighted spaces, where the role of all variables and groups of variables is the same. For weighted spaces one can monitor the role of all variables and groups of variables. Necessary and sufficient conditions on the decay of the weights are given to obtain various notions of tractability.

The text contains extensive chapters on discrepancy and integration, decomposable kernels and lower bounds, the Smolyak/sparse grid algorithms, lattice rules and the CBC (component-by-component) algorithms. This is done in various settings. Path integration and quantum computation are also discussed.

The book is of interest for researchers working in computational mathematics, especially in approximation of high-dimensional problems. It is also well suited for graduate courses and seminars. 61 open problems are listed to stimulate future research in tractability.

Keywords: Discrepancy, lattice rules, Smolyak/sparse grid algorithms, decomposable reproducing kernels, curse of dimensionality, tractability, high-dimensional numerical problems, worst case, average case, probabilistic and randomized settings, weighted spaces

Further Information

Review in Zentralblatt MATH 1241.65025

Review in MR 2676032 (2011h:46093)