Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions

DOI10.1016/J.JCO.2016.10.002zbMATH Open1359.65008arXiv1505.02003OpenAlexW2531036618MaRDI QIDQ511114FDOQ511114

Kosuke Suzuki

Publication date: 14 February 2017

Published in: Journal of Complexity (Search for Journal in Brave)

Abstract: We investigate multivariate integration for a space of infinitely times differentiable functions $$, where $$, $$ and $$ is a sequence of positive decreasing weights. Let $e(n,s)$ be the minimal worst-case error of all algorithms that use $n$ function values in the $s$-variate case. We prove that for any $$ and $s$ considered $e(n,s)leqC(s)exp(-c(s)(logn{)}^2)$ holds for all $n$, where $C(s)$ and $c(s)$ are constants which may depend on $s$. Further we show that if the weights $$ decay sufficiently fast then there exist some $1<p<2$ and absolute constants $C$ and $c$ such that $e(n,s)leqCexp(-c(logn{)}^p)$ holds for all $s$ and $n$. These bounds are attained by quasi-Monte Carlo integration using digital nets. These convergence and tractability results come from those for the Walsh space into which $$ is embedded.

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

zbMATH Keywords

convergencenumerical integrationquasi-Monte Carlodigital netstractabilitysuper-polynomial convergenceWalsh spaces

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical quadrature and cubature formulas (65D32) Multidimensional problems (41A63) Approximate quadratures (41A55)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Formulas for the Walsh coefficients of smooth functions and their application to bounds on the Walsh coefficients
• Walsh Spaces Containing Smooth Functions and Quasi–Monte Carlo Rules of Arbitrary High Order
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
• Integration in Hermite spaces of analytic functions
• Exponential convergence and tractability of multivariate integration for Korobov spaces
• Multivariate integration of infinitely many times differentiable functions in weighted Korobov spaces
• Tractability of multivariate problems. Volume III: Standard information for operators
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• A Taylor space for multivariate integration
• Quasi-Monte Carlo point sets with small \(t\)-values and WAFOM
• Existence of Higher Order Convergent Quasi-Monte Carlo Rules via Walsh Figure of Merit
• A computable figure of merit for quasi-Monte Carlo point sets
• WAFOM over abelian groups for quasi-Monte Carlo point sets
• Interpolation and approximation in Taylor spaces
• The curse of dimensionality for numerical integration of smooth functions. II

Cited In (10)

• Selected aspects of tractability analysis
• Simple characterizations of exponential tractability for linear multivariate problems
• EC-tractability of approximation problems in function spaces defined over products of simplices
• Super-polynomial accuracy of one dimensional randomized nets using the median of means
• A Universal Median Quasi-Monte Carlo Integration
• Exponential convergence of an approximation problem for infinitely differentiable multivariate functions
• Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals
• A search for extensible low-WAFOM point sets
• Construction of interlaced polynomial lattice rules for infinitely differentiable functions
• Approximation of quasi-Monte Carlo worst case error in weighted spaces of infinitely times smooth functions

This page was built for publication: Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions

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