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 methodmultivariate integrationoptimal order of convergencequadrature rulerandomized errorrandomized Frolov algorithmSobolev spacesworst-case error

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

• Cubature formulas, discrepancy, and nonlinear approximation
• Deterministic and stochastic error bounds in numerical analysis
• 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?)
• 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

(35)

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

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)