Explicit Constructions of Quasi-Monte Carlo Rules for the Numerical Integration of High-Dimensional Periodic Functions

By Josef Dick. 2007

88 citations recorded by the source corpus.

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, for every even integer $\alpha \ge 1$, is of ${\cal O}(N^{-\min(\alpha,d)} (\log N)^{s\alpha-2})$, 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 the 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 $\mathbb{Z}_b$.

Subfields: Applied Mathematics, Numerical Analysis, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Numerical Analysis

In Statistics and Probability

Citations in the corpus

Convergence guarantees for kernel-based quadrature rules in misspecified settings (2016, background): “We also note that there are certain quadratures which are adaptive to less smooth integrands [8, 9, 10].”
Monte Carlo and Quasi-Monte Carlo Sampling (2009, background): “Finally, another line of research that has been pursued recently is to construct digital nets and sequences that work well for integrands belonging to certain classes of smooth functions [77, 78].”
Walsh Spaces Containing Smooth Functions and Quasi-Monte Carlo Rules of Arbitrary High Order (2008, unknown): “First we generalize the digital ( t, α, β, m, s )-nets used in [2] to digital ( t, α, β, n × m, s )-nets and show that we then can remove the periodicity assumption necessary in [2].”
Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration (2010, background): “A general theory of higher order digital nets and sequences has been developed in [36] for periodic functions, and for the general case in [37].”
Hyperbolic Cross Approximation (2016, methodology): “21 we need to use higher order digital nets as recently introduced by Dick [79].”
Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands (2010, unknown): “The underlying idea of the new randomized QMC algorithm stems from [3, 4].”
Discrepancy Theory and Quasi-Monte Carlo Integration (2014, unknown): “Furthermore, explicit constructions can be obtained using the method from [17, 18] introduced above.”