Tractability of multivariate problems. Volume III: Standard information for operators (Q715694)

This is the third, and final, volume of the extensive monograph on tractability of multivariate problems. For reviews of previous volumes see [Volume I: Linear information. Zürich: European Mathematical Society (EMS) (2008; Zbl 1156.65001)] and [Volume II: Standard information for functionals. Zürich: European Mathematical Society (EMS) (2010; Zbl 1241.65025)]. Recall that the first volume primarily studies multivariate problems specified by linear operators and algorithms that use linear information \(\Lambda^{all}\) given by arbitrary continuous linear functionals. In the second volume, the authors study multivariate problems specified by linear functionals and a few nonlinear functionals, and algorithms that use standard information \(\Lambda^{std}\) given by function values. Finally, in the third volume, multivariate problems specified by linear operators and a few nonlinear operators, and algorithms that use mainly standard information \(\Lambda^{std}\) are studied. The problems studied in all three volumes are defined on spaces of \(d\)-variate functions, \(d\) being often very large, perhaps even arbitrarily large. Such a \(d\)-variate problem is tractable if we can approximate it with errors at most \(\varepsilon\), using a number of linear functionals from \(\Lambda^{all}\) or \(\Lambda^{std}\) that is not exponential either in \(d\) or \(\varepsilon^{-1}\). In this volume, tractability results in the worst case and randomized setting are presented, both cases for absolute and normalized error criteria. Probability setting and relative error criteria are not covered. First, multivariate approximations are analyzed. Knowing the results for them, the authors turn to study general linear problems which are specified by linear multivariate operators, which are approximated by modified algorithms for multivariate approximation or, by modifications of the Smolyak/sparse grid algorithm, which has been already studied in Volume II [loc. cit.]. One chapter deals with a few selected nonlinear problems. Instead developing tractability theory for arbitrary nonlinear problems, being an impracticable task, the authors treat each problem as its own and restrict their attention to the worst case setting. The list of 149 open problems is a good indicator of what else need to be done in the future.