Richardson extrapolation of polynomial lattice rules

DOI10.1137/17M1138601MaRDI QIDQ4646439zbMATH OpenOpenAlexWikidataFDO

Authors Josef Dick, Takashi Goda, Takehito Yoshiki

Publication date 14 January 2019

Published in SIAM Journal on Numerical Analysis (Search for Journal in Brave)

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

zbMATH Keywords

componenet-by-component constructionpolynomial lattice rulequasi-Monte CarloRichardson extrapolation

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical integration (65D30) Numerical quadrature and cubature formulas (65D32)

Abstract: We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness $alphageq2$ 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},ldots,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)NlogN$, which improves the currently known result for interlaced polynomial lattice rule, that is of order $salphaNlogN$. 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.

Recommendations

• Extrapolated polynomial lattice rule integration in computational uncertainty quantification
• Richardson extrapolation allows truncation of higher-order digital nets and sequences
• Construction of interlaced polynomial lattice rules for infinitely differentiable functions
• Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces
• Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules

Cites work

• Bounds on Walsh coefficients by dyadic difference and a new Koksma-Hlawka type inequality for quasi-Monte Carlo integration
• Computational higher order quasi-Monte Carlo integration
• Construction algorithms for higher order polynomial lattice rules
• Construction of interlaced scrambled polynomial lattice rules of arbitrary high order
• Digital nets with infinite digit expansions and construction of folded digital nets for quasi-Monte Carlo integration
• Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules
• Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
• Fast component-by-component construction, a reprise for different kernels
• Fast QMC matrix-vector multiplication
• Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces
• High-dimensional integration: The quasi-Monte Carlo way
• Higher order QMC Petrov-Galerkin discretization for affine parametric operator equations with random field inputs
• Higher order quasi-Monte Carlo integration for holomorphic, parametric operator equations
• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 3854294 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 914714 (Why is no real title available?)
• Low-discrepancy point sets obtained by digital constructions over finite fields
• Multilevel Richardson-Romberg extrapolation
• Numerical analysis.
• QMC rules of arbitrary high order: Reproducing kernel Hilbert space approach
• Quasi-Monte Carlo integration using digital nets with antithetics
• Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules
• The decay of the Walsh coefficients of smooth functions
• 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?

Cited in

(9)

• The existence of good extensible polynomial lattice rules
• Lattice rules in non-periodic subspaces of Sobolev spaces
• Adaptive quasi-Monte Carlo finite element methods for parametric elliptic PDEs
• Very basic multidimensional extrapolation quadrature
• Higher-order quasi-Monte Carlo training of deep neural networks
• Extrapolated polynomial lattice rule integration in computational uncertainty quantification
• Richardson extrapolation allows truncation of higher-order digital nets and sequences
• A Universal Median Quasi-Monte Carlo Integration
• A-posteriori QMC-FEM error estimation for Bayesian inversion and optimal control with entropic risk measure

This page was built for publication: Richardson extrapolation of polynomial lattice rules

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