Construction of interlaced polynomial lattice rules for infinitely differentiable functions

Abstract

We study multivariate integration over the $s$-dimensional unit cube in a weighted space of infinitely differentiable functions. It is known from a recent result by Suzuki that there exists a good quasi-Monte Carlo (QMC) rule which achieves a super-polynomial convergence of the worst-case error in this function space, and moreover, that this convergence behavior is independent of the dimension under a certain condition on the weights. In this paper we provide a constructive approach to finding a good QMC rule achieving such a dimension-independent super-polynomial convergence of the worst-case error. Specifically, we prove that interlaced polynomial lattice rules, with an interlacing factor chosen properly depending on the number of points $N$ and the weights, can be constructed using a fast component-by-component algorithm in at most $O(sN(\log N{)}^2)$ arithmetic operations to achieve a dimension-independent super-polynomial convergence. The key idea for the proof of the worst-case error bound is to use a variant of Jensen's inequality with a purposely-designed concave function.

References in corpus (4)

• The decay of the Walsh coefficients of smooth functions
• Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions
• WAFOM on abelian groups for quasi-Monte Carlo point sets
• Formulas for the Walsh coefficients of smooth functions and their application to bounds on the Walsh coefficients

Cited by in corpus (2)

• A universal median quasi-Monte Carlo integration
• Recent advances in higher order quasi-Monte Carlo methods