Tractability of multivariate problems. Volume I: Linear information (Q940799)

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.