Richardson extrapolation of polynomial lattice rules

Abstract

We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness $\alpha \ge 2$ defined over the $s$-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named \emph{extrapolated polynomial lattice rule}, which achieves the almost optimal rate of convergence. Extrapolated polynomial lattice rules are constructed in two steps: i) construction of classical polynomial lattice rules over ${\mathbb{F}}_b$ with $\alpha$ consecutive sizes of nodes, $b^{m-\alpha +1},\dots ,b^m$, and ii) recursive application of Richardson extrapolation to a chain of $\alpha$ approximate values of the integral obtained by consecutive polynomial lattice rules. We prove the existence of good extrapolated polynomial lattice rules achieving the almost optimal order of convergence of the worst-case error in Sobolev spaces with general weights. Then, by restricting to product weights, we show that such good extrapolated polynomial lattice rules can be constructed by the fast component-by-component algorithm under a computable quality criterion. The required total construction cost is of order $(s+\alpha )N\log N$, which improves the currently known result for interlaced polynomial lattice rule, that is of order $s\alpha N\log N$. We also study the dependence of the worst-case error bound on the dimension. A big advantage of our method compared to interlaced polynomial lattice rules is that the fast QMC matrix vector method can be used in this setting, while still achieving the same rate of convergence. Such a method was previously not known. Numerical experiments for test integrands support our theoretical result.

References in corpus (9)

• Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order
• Higher order QMC Galerkin discretization for parametric operator equations
• Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules
• Construction of interlaced scrambled polynomial lattice rules of arbitrary high order
• Multilevel Richardson-Romberg extrapolation
• Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces
• The decay of the Walsh coefficients of smooth functions
• Digital nets with infinite digit expansions and construction of folded digital nets for quasi-Monte Carlo integration
• Quasi-Monte Carlo integration using digital nets with antithetics

Cited by in corpus (5)

• Lattice rules in non-periodic subspaces of Sobolev spaces
• A universal median quasi-Monte Carlo integration
• Recent advances in higher order quasi-Monte Carlo methods
• Higher-order Quasi-Monte Carlo Training of Deep Neural Networks
• Richardson extrapolation allows truncation of higher order digital nets and sequences