Average case complexity of multivariate integration for smooth functions

From MaRDI portal





The computational complexity of multivariate integration is determined as the average case setting, in which cost and error of the approximating multivariate integrals are defined as the expected cost and error with respect to the folded Wiener sheet measure on the class of smooth functions. This average case complexity is derived by using a relation between the average and worst case settings. The main result of the paper is the evaluation of the average case complexity of an optimal algorithm for multivariate integration, where the computation of the optimal sample points, as well as their number, requires preprocessing which increases the computation cost. Also, a different set of fully constructive almost optimal points (that can be preprocessed by using the Monte Carlo algorithm) and an almost optimal algorithm are given with a reduced average case complexity.




Cited in
(32)








This page was built for publication: Average case complexity of multivariate integration for smooth functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1260659)