A universal algorithm for multivariate integration

DOI10.1007/S10208-016-9307-YMaRDI QIDQ2407672zbMATH OpenOpenAlexFDO

Authors David Krieg, Erich Novak

Publication date 6 October 2017

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.06853

zbMATH Keywords

Monte Carlo methodSobolev spacesquadrature rulemultivariate integrationworst-case erroroptimal order of convergencerandomized errorrandomized Frolov algorithm

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Random number generation in numerical analysis (65C10) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25)

Abstract: We present an algorithm for multivariate integration over cubes that is unbiased and has optimal order of convergence (in the randomized sense as well as in the worst case setting) for all Sobolev spaces $H^{r,mix}([0,1{]}^d)$ and $H^s([0,1{]}^d)$ for $s>d/2$.

Recommendations

• Randomized Smolyak algorithms based on digital sequences for multivariate integration
• High dimensional integration of smooth functions over cubes
• A Monte Carlo method for integration of multivariate smooth functions
• On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation
• Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition

Cites work

• scientific article; zbMATH DE number 3558807 (Why is no real title available?)
• scientific article; zbMATH DE number 721668 (Why is no real title available?)
• scientific article; zbMATH DE number 1049042 (Why is no real title available?)
• scientific article; zbMATH DE number 1489555 (Why is no real title available?)
• Cubature formulas, discrepancy, and nonlinear approximation
• Deterministic and stochastic error bounds in numerical analysis
• My dream quadrature rule
• The role of Frolov's cubature formula for functions with bounded mixed derivative
• Tractability of multivariate problems. Volume II: Standard information for functionals.

Cited in

(31)

• Recovery of Sobolev functions restricted to iid sampling
• General algorithm for the numerical integration of functions of several variables
• Optimal confidence for Monte Carlo integration of smooth functions
• A Monte Carlo algorithm for weighted integration over $\mathbb {R}^d$
• A note on the dispersion of admissible lattices
• The role of Frolov's cubature formula for functions with bounded mixed derivative
• Some results on the complexity of numerical integration
• Complexity of Monte Carlo integration for Besov classes on the unit sphere
• Integration of monotone functions of several variables
• Linear Monte Carlo quadrature with optimal confidence intervals
• Optimal Monte Carlo methods for \(L^2\)-approximation
• scientific article; zbMATH DE number 2051231 (Why is no real title available?)
• Monte Carlo method for numerical integration based on Sobol's sequences
• Change of variable in spaces of mixed smoothness and numerical integration of multivariate functions on the unit cube
• A Monte Carlo method for integration of multivariate smooth functions
• Lattice rules with random \(n\) achieve nearly the optimal \(\mathcal{O}(n^{-\alpha-1/2})\) error independently of the dimension
• An algorithm-driven approach to error analysis for multidimensional integration
• Random-prime-fixed-vector randomised lattice-based algorithm for high-dimensional integration
• Optimal randomized quadrature for weighted Sobolev and Besov classes with the Jacobi weight on the ball
• On polynomial-time property for a class of randomized quadratures
• Higher-Order Monte Carlo through Cubic Stratification
• scientific article; zbMATH DE number 2051207 (Why is no real title available?)
• Weighted least \(\ell_p\) approximation on compact Riemannian manifolds
• Optimal order quadrature error bounds for infinite-dimensional higher-order digital sequences
• Exact Error Estimates and Optimal Randomized Algorithms for Integration
• Consistency of randomized integration methods
• On the orthogonality of the Chebyshev-Frolov lattice and applications
• A Universal Median Quasi-Monte Carlo Integration
• Extensions of the AZ-Algorithm and the Package MultiIntegrate
• On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation
• Numerical performance of optimized Frolov lattices in tensor product reproducing kernel Sobolev spaces

This page was built for publication: A universal algorithm for multivariate integration

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