Explicit constructions of quasi-Monte Carlo rules for the numerical integration of high dimensional periodic functions

Abstract

In this paper we give explicit constructions of point sets in the $s$ dimensional unit cube yielding quasi-Monte Carlo algorithms which achieve the optimal rate of convergence of the worst-case error for numerically integrating high dimensional periodic functions. In the classical measure $P_{\alpha }$ of the worst-case error introduced by Korobov the convergence is of $\landau(N^{-\min(α,d)} (\log N)^{sα-2})$ for every even integer $\alpha \ge 1$, where $d$ is a parameter of the construction which can be chosen arbitrarily large and $N$ is the number of quadrature points. This convergence rate is known to be best possible up to some $\log N$ factors. We prove the result for the deterministic and also a randomized setting. The construction is based on a suitable extension of digital $(t,m,s)$-nets over the finite field $\integer_b$.

Cited by in corpus (20)

• Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order
• Higher order QMC Galerkin discretization for parametric operator equations
• Construction of interlaced scrambled polynomial lattice rules of arbitrary high order
• From van der Corput to modern constructions of sequences for quasi-Monte Carlo rules
• Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces
• The decay of the Walsh coefficients of smooth functions
• Optimal quasi-Monte Carlo rules on order 2 digital nets for the numerical integration of multivariate periodic functions
• Optimal order quasi-Monte Carlo integration in weighted Sobolev spaces of arbitrary smoothness
• An explicit construction of optimal order quasi-Monte Carlo rules for smooth integrands
• Optimal order quadrature error bounds for infinite-dimensional higher order digital sequences
• Formulas for the Walsh coefficients of smooth functions and their application to bounds on the Walsh coefficients
• Quasi-Monte Carlo point sets with small $t$-values and WAFOM
• A search for extensible low-WAFOM point sets
• The $b$-adic tent transformation for quasi-Monte Carlo integration using digital nets
• Construction of interlaced polynomial lattice rules for infinitely differentiable functions
• Optimal $L_p$-discrepancy bounds for second order digital sequences
• Fast construction of higher order digital nets for numerical integration in weighted Sobolev spaces
• Quasi-Monte Carlo for unbounded integrands with importance sampling
• Richardson extrapolation allows truncation of higher order digital nets and sequences
• Constructing good higher order polynomial lattice rules with modulus of reduced degree