Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1707.03989 · SIAM Journal on Numerical Analysis

Richardson Extrapolation of Polynomial Lattice Rules

Josef Dick, Takashi Goda, Takehito Yoshiki

Published Jan 1, 2019• 11 citations
arXivHTMLPDF

Abstract

We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness $\alpha\geq 2$ defined over the $s$-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named the 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 $\Bbb{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)N\log N$, which improves the currently known result for the interlaced polynomial lattice rule, which 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.

DOI
10.1137/17m1138601

Related papers

Extrapolated Polynomial Lattice Rule Integration in Computational Uncertainty Quantification

Josef Dick, Marcello Longo, Christoph Schwab

Abstract. We present an extension of the convergence analysis for Richardson-extrapolated polynomial lattice rules from [J. Dick, T. Goda, and T. Yoshiki, SIAM J. Numer. Anal., 57 (2019), pp. 44–69] for high-dimensional, numerical integration to classes of integrand functions with quantified smoothness and quasi–Monte Carlo (QMC) integration rules with so-called smoothness-driven, product and order dependent (SPOD) weights. We establish in particular sufficient conditions for the existence of an asymptotic expansion of the QMC integration error with respect to suitable powers of N, the number of QMC integration nodes. We derive a dimension-separated criterion for a fast component-by-component (CBC) construction algorithm for the computation of the QMC generating vector with quadratic scaling with respect to the integration dimension s. We prove that the proposed QMC integration strategies (a) are free from the curse of dimensionality, (b) afford higher-order convergence rates subject to suitable summability conditions on the QMC weights, (c) allow for certain classes of high-dimensional integrand functions a computable, asymptotically exact numerical estimate of the QMC quadrature error, with reliability and efficiency independent of the dimension of the integration domain, and (d) accommodate fast, FFT-based matrix-vector multiplication from [J. Dick, F. Y. Kuo, Q. T. Le Gia, C. Schwab, SIAM J. Sci. Comput., 37 (2015), pp. A1436–A1450] when applied to parametric operator equations. The integration methods are applicable for large classes of many-parametric integrand functions with quantified parametric smoothness. We verify all hypotheses and present numerical examples arising from the Galerkin finite-element discretization of a model linear parametric elliptic PDE illustrating (a)–(d). We verify computationally the scaling of the fast CBC construction algorithm with SPOD QMC weights and examine the extrapolation-based a posteriori numerical estimation of the QMC quadrature error. We find in examples with parameter spaces of dimension s = 10, …, 128 that the extrapolation-based, computable QMC integration error indicator has an efficiency index between 0.9 and 1.1 for a moderate number N of QMC points.

SIAM/ASA Journal on Uncertainty Quantification•Jun 29, 2022•3 citations

Construction-Free Median Quasi-Monte Carlo Rules for Function Spaces with Unspecified Smoothness and General Weights

Takashi Goda, Pierre L’Ecuyer

We study quasi-Monte Carlo (QMC) integration of smooth functions defined over the multidimensional unit cube. Inspired by a recent work of Pan and Owen, we study a new construction-free median QMC rule which can exploit the smoothness and the weights of function spaces adaptively. For weighted Korobov spaces, we draw a sample of $r$ independent generating vectors of rank-1 lattice rules, compute the integral estimate for each, and approximate the true integral by the median of these $r$ estimates. For weighted Sobolev spaces, we use the same approach but with the rank-1 lattice rules replaced by high-order polynomial lattice rules. A major advantage over the existing approaches is that we do not need to construct good generating vectors by a computer search algorithm, while our median QMC rule achieves almost the optimal worst-case error rate for the respective function space with any smoothness and weights, with a probability that converges to 1 exponentially fast as $r$ increases. Numerical experiments illustrate and support our theoretical findings.

arXiv:2201.09413•SIAM Journal on Scientific Computing•Aug 1, 2022•25 citations

A Universal Median Quasi-Monte Carlo Integration

Takashi Goda, Kosuke Suzuki, Makoto Matsumoto

Abstract. We study quasi-Monte Carlo (QMC) integration over the multidimensional unit cube in several weighted function spaces with different smoothness classes. We consider approximating the integral of a function by the median of several integral estimates under independent and random choices of the underlying QMC point sets (either linearly scrambled digital nets or infinite-precision polynomial lattice point sets). Even though our approach does not require any information on the smoothness and weights of a target function space as an input, we can prove a probabilistic upper bound on the worst-case error for the respective weighted function space, where the failure probability converges to 0 exponentially fast as the number of estimates increases. Our obtained rates of convergence are nearly optimal for function spaces with finite smoothness, and we can attain a dimension-independent super-polynomial convergence for a class of infinitely differentiable functions. This implies that our median-based QMC rule is universal in the sense that it does not need to be adjusted to the smoothness and the weights of the function spaces and yet exhibits the nearly optimal rate of convergence. Numerical experiments support our theoretical results.

arXiv:2209.13186•SIAM Journal on Numerical Analysis•Feb 16, 2024•12 citations

Quasi-Monte Carlo methods for high-dimensional integration: the standard (weighted Hilbert space) setting and beyond

F. Y. Kuo, Christoph Schwab, I. H. Sloan

This paper is a contemporary review of quasi-Monte Carlo (QMC) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube \([0,1]^s\). It first introduces the by-now standard setting of weighted Hilbert spaces of functions with square-integrable mixed first derivatives, and then indicates alternative settings, such as non-Hilbert spaces, that can sometimes be more suitable. Original contributions include the extension of the fast component-by-component (CBC) construction of lattice rules that achieve the optimal convergence order (a rate of almost \(1/N\), where \(N\) is the number of points, independently of dimension) to so-called “product and order dependent” (POD) weights, as seen in some recent applications. Although the paper has a strong focus on lattice rules, the function space settings are applicable to all QMC methods. Furthermore, the error analysis and construction of lattice rules can be adapted to polynomial lattice rules from the family of digital nets. doi:10.1017/S1446181112000077

ANZIAM Journal•May 21, 2012•4 citations

Constructive approaches to quasi-Monte Carlo methods for multiple integration

Frances Y. Kuo

Recently, quasi-Monte Carlo methods have been successfully used for approximating multiple integrals in hundreds of dimensions in mathematical finance, and were significantly more efficient than Monte Carlo methods. To understand the apparent success of quasi-Monte Carlo methods for multiple integration, one popular approach is to study worst-case error bounds in weighted function spaces in which the importance of the variables is moderated by some sequences of weights. Ideally, a family of quasi-Monte Carlo methods in some weighted function space should be strongly tractable. Strong tractability means that the minimal number of quadrature points n needed to reduce the initial error by a factor of ε is bounded by a polynomial in ε⁻¹ independently of the dimension d. Several recent publications show the existence of lattice rules that satisfy the strong tractability error bounds in weighted Korobov spaces of periodic integrands and weighted Sobolev spaces of non-periodic integrands. However, those results were non-constructive and thus give no clues as to how to actually construct these lattice rules. In this thesis, we focus on the construction of quasi-Monte Carlo methods that are strongly tractable. We develop and justify algorithms for the construction of lattice rules that achieve strong tractability error bounds in weighted Korobov and Sobolev spaces. The parameters characterizing these lattice rules are found ‘component-by-component’: the (d + 1)-th components are obtained by successive 1-dimensional searches, with the previous d components kept unchanged. The cost of these algorithms vary from O(nd²) to O(n³d²) operations. With currently available technology, they allow construction of rules easily with values of n up to several million and dimensions d up to several hundred.

•Jan 1, 2002•2 citations

On the step-by-step construction of quasi–Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces

Ian H. Sloan, Frances Y. Kuo, Stephen Joe

We develop and justify an algorithm for the construction of quasi–Monte Carlo (QMC) rules for integration in weighted Sobolev spaces; the rules so constructed are shifted rank-1 lattice rules. The parameters characterising the shifted lattice rule are found “component-by-component”: the ( d + 1 d+1 )-th component of the generator vector and the shift are obtained by successive 1 1 -dimensional searches, with the previous d d components kept unchanged. The rules constructed in this way are shown to achieve a strong tractability error bound in weighted Sobolev spaces. A search for n n -point rules with n n prime and all dimensions 1 to d d requires a total cost of O ( n 3 d 2 ) O(n^3d^2) operations. This may be reduced to O ( n 3 d ) O(n^3d) operations at the expense of O ( n 2 ) O(n^2) storage. Numerical values of parameters and worst-case errors are given for dimensions up to 40 and n n up to a few thousand. The worst-case errors for these rules are found to be much smaller than the theoretical bounds.

Mathematics of Computation•Mar 20, 2002•91 citations
We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness α≥2\alpha\geq 2α≥2 defined over the sss-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named the 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 Fb\Bbb{F}_bFb​ with α\alphaα consecutive sizes of nodes, bm−α+1,…,bmb^{m-\alpha+1},\ldots,b^{m}bm−α+1,…,bm, 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+α)Nlog⁡N(s+\alpha)N\log N(s+α)NlogN, which improves the currently known result for the interlaced polynomial lattice rule, which is of order sαNlog⁡Ns\alpha N\log NsαNlogN. 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.
Abstract. We present an extension of the convergence analysis for Richardson-extrapolated polynomial lattice rules from [J. Dick, T. Goda, and T. Yoshiki, SIAM J. Numer. Anal., 57 (2019), pp. 44–69] for high-dimensional, numerical integration to classes of integrand functions with quantified smoothness and quasi–Monte Carlo (QMC) integration rules with so-called smoothness-driven, product and order dependent (SPOD) weights. We establish in particular sufficient conditions for the existence of an asymptotic expansion of the QMC integration error with respect to suitable powers of N, the number of QMC integration nodes. We derive a dimension-separated criterion for a fast component-by-component (CBC) construction algorithm for the computation of the QMC generating vector with quadratic scaling with respect to the integration dimension s. We prove that the proposed QMC integration strategies (a) are free from the curse of dimensionality, (b) afford higher-order convergence rates subject to suitable summability conditions on the QMC weights, (c) allow for certain classes of high-dimensional integrand functions a computable, asymptotically exact numerical estimate of the QMC quadrature error, with reliability and efficiency independent of the dimension of the integration domain, and (d) accommodate fast, FFT-based matrix-vector multiplication from [J. Dick, F. Y. Kuo, Q. T. Le Gia, C. Schwab, SIAM J. Sci. Comput., 37 (2015), pp. A1436–A1450] when applied to parametric operator equations. The integration methods are applicable for large classes of many-parametric integrand functions with quantified parametric smoothness. We verify all hypotheses and present numerical examples arising from the Galerkin finite-element discretization of a model linear parametric elliptic PDE illustrating (a)–(d). We verify computationally the scaling of the fast CBC construction algorithm with SPOD QMC weights and examine the extrapolation-based a posteriori numerical estimation of the QMC quadrature error. We find in examples with parameter spaces of dimension s = 10, …, 128 that the extrapolation-based, computable QMC integration error indicator has an efficiency index between 0.9 and 1.1 for a moderate number N of QMC points.
We study quasi-Monte Carlo (QMC) integration of smooth functions defined over the multidimensional unit cube. Inspired by a recent work of Pan and Owen, we study a new construction-free median QMC rule which can exploit the smoothness and the weights of function spaces adaptively. For weighted Korobov spaces, we draw a sample of rrr independent generating vectors of rank-1 lattice rules, compute the integral estimate for each, and approximate the true integral by the median of these rrr estimates. For weighted Sobolev spaces, we use the same approach but with the rank-1 lattice rules replaced by high-order polynomial lattice rules. A major advantage over the existing approaches is that we do not need to construct good generating vectors by a computer search algorithm, while our median QMC rule achieves almost the optimal worst-case error rate for the respective function space with any smoothness and weights, with a probability that converges to 1 exponentially fast as rrr increases. Numerical experiments illustrate and support our theoretical findings.
Abstract. We study quasi-Monte Carlo (QMC) integration over the multidimensional unit cube in several weighted function spaces with different smoothness classes. We consider approximating the integral of a function by the median of several integral estimates under independent and random choices of the underlying QMC point sets (either linearly scrambled digital nets or infinite-precision polynomial lattice point sets). Even though our approach does not require any information on the smoothness and weights of a target function space as an input, we can prove a probabilistic upper bound on the worst-case error for the respective weighted function space, where the failure probability converges to 0 exponentially fast as the number of estimates increases. Our obtained rates of convergence are nearly optimal for function spaces with finite smoothness, and we can attain a dimension-independent super-polynomial convergence for a class of infinitely differentiable functions. This implies that our median-based QMC rule is universal in the sense that it does not need to be adjusted to the smoothness and the weights of the function spaces and yet exhibits the nearly optimal rate of convergence. Numerical experiments support our theoretical results.
This paper is a contemporary review of quasi-Monte Carlo (QMC) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1]s[0,1]^s[0,1]s. It first introduces the by-now standard setting of weighted Hilbert spaces of functions with square-integrable mixed first derivatives, and then indicates alternative settings, such as non-Hilbert spaces, that can sometimes be more suitable. Original contributions include the extension of the fast component-by-component (CBC) construction of lattice rules that achieve the optimal convergence order (a rate of almost 1/N1/N1/N, where NNN is the number of points, independently of dimension) to so-called “product and order dependent” (POD) weights, as seen in some recent applications. Although the paper has a strong focus on lattice rules, the function space settings are applicable to all QMC methods. Furthermore, the error analysis and construction of lattice rules can be adapted to polynomial lattice rules from the family of digital nets. doi:10.1017/S1446181112000077
Recently, quasi-Monte Carlo methods have been successfully used for approximating multiple integrals in hundreds of dimensions in mathematical finance, and were significantly more efficient than Monte Carlo methods. To understand the apparent success of quasi-Monte Carlo methods for multiple integration, one popular approach is to study worst-case error bounds in weighted function spaces in which the importance of the variables is moderated by some sequences of weights. Ideally, a family of quasi-Monte Carlo methods in some weighted function space should be strongly tractable. Strong tractability means that the minimal number of quadrature points n needed to reduce the initial error by a factor of ε is bounded by a polynomial in ε⁻¹ independently of the dimension d. Several recent publications show the existence of lattice rules that satisfy the strong tractability error bounds in weighted Korobov spaces of periodic integrands and weighted Sobolev spaces of non-periodic integrands. However, those results were non-constructive and thus give no clues as to how to actually construct these lattice rules. In this thesis, we focus on the construction of quasi-Monte Carlo methods that are strongly tractable. We develop and justify algorithms for the construction of lattice rules that achieve strong tractability error bounds in weighted Korobov and Sobolev spaces. The parameters characterizing these lattice rules are found ‘component-by-component’: the (d + 1)-th components are obtained by successive 1-dimensional searches, with the previous d components kept unchanged. The cost of these algorithms vary from O(nd²) to O(n³d²) operations. With currently available technology, they allow construction of rules easily with values of n up to several million and dimensions d up to several hundred.
We develop and justify an algorithm for the construction of quasi–Monte Carlo (QMC) rules for integration in weighted Sobolev spaces; the rules so constructed are shifted rank-1 lattice rules. The parameters characterising the shifted lattice rule are found “component-by-component”: the ( d + 1 d+1 )-th component of the generator vector and the shift are obtained by successive 1 1 -dimensional searches, with the previous d d components kept unchanged. The rules constructed in this way are shown to achieve a strong tractability error bound in weighted Sobolev spaces. A search for n n -point rules with n n prime and all dimensions 1 to d d requires a total cost of O ( n 3 d 2 ) O(n^3d^2) operations. This may be reduced to O ( n 3 d ) O(n^3d) operations at the expense of O ( n 2 ) O(n^2) storage. Numerical values of parameters and worst-case errors are given for dimensions up to 40 and n n up to a few thousand. The worst-case errors for these rules are found to be much smaller than the theoretical bounds.