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.
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 multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness α≥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 Fb with α consecutive sizes of nodes, bm−α+1,…,bm, and (ii) recursive application of Richardson extrapolation to a chain of α 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+α)NlogN, which improves the currently known result for the interlaced polynomial lattice rule, which is of order sα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.
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
Abstract 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.
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.
In this talk I will show the beautiful simplicity of approximating high-dimensional integrals using lattice rules. In current engineering applications it is relatively easy to come up with very high and ultra high dimensional integrals, which might be expectations, that depend on hundreds, thousands, or even an infinite number of variables. As the minimal non-trivial tensor product rule, constructed from a 2-point rule, in 100 dimensions already uses 2^{100} = 1267650600228229401496703205376 ≈ 10^{30} function evaluations—which would take 10^{24} seconds at 1 function evaluation per microsecond and we remember the age of the universe to be only approximately 10^{17} seconds—we all know why to use Monte Carlo or quasi-Monte Carlo methods where we can freely choose the number of function evaluations independent of the number of dimensions. While plain vanilla Monte Carlo methods are very robust and easy to apply, in the case of quasi-Monte Carlo methods a lot more details can pop up. I will first introduce the most elegant—in my biased opinion, which I will defend—of all quasi-Monte Carlo methods: the rank-1 lattice rule. This method is defined by one single integer generating vector together with the total number of points in the rule. Approximating a multivariate integral by this method can be done in one line of Matlab code! As one is often interested in successive approximations I will next introduce a rank-1 lattice sequence. Maybe surprisingly, also here, one simple line of Matlab code is sufficient to calculate a segment of a lattice sequence (with a special property). While for Monte Carlo integration the usual assumption is L2 integrability, leading to an error bound of O(N^{−1/2}). For quasi-Monte Carlo methods we generally work with more involved function space settings, leading to error bounds of the form O(N^{−α}) with α ≥ 1/2. I will show the standard function space settings and dive into the weighted function spaces which are being used in current theory to be able to make the error bounds independent of the number of dimensions. We will gloss over the Korobov space of periodic smooth functions, the unanchored Sobolev space with first mixed derivatives, and the cosine space which is a special space of smooth non-periodic functions. All of which are spaces of so-called mixed dominating smoothness, which in terms of mixed derivatives would mean ∂^{k_1+···+k_s} /(∂x_1^{k_1} · · · ∂x_s^{k_s}) exists for all (k_1, . . . , k_s) ≤ (α, . . . , α). For non-periodic function spaces lattice rules and sequences can only reach O(N^{−1}) convergence. To arrive at higher-order convergence of O(N^{−α}) for non-periodic functions we dive into higher-order Sobolev spaces (of mixed dominating smoothness) in combination with digital nets, but here disguised as a lattice rule, namely polynomial lattice rules. Here, all arithmetic is over a finite field (we will choose the one of order 2) and our lattice rules now take the form of a lattice of polynomials which we map back to points in the unit cube. Higher order can now be obtained by means of the interlacing method from Josef Dick. Although more complicated, again, given the generating matrices of the digital net (as a bunch of integers), and two lines for a magical de Bruijn sequence, we can approximate an integral by such a digital sequence with a single line of (complicated) Matlab code. While Matlab/Octave one-liners might be fun, and somehow instructive, I will also point you to my online resources where code is available to (a) construct good lattice rules, lattice sequences and polynomial lattice rules (for product, order-dependent, product-and-order-dependent aka POD, and smoothness-driven product-and-order dependent aka SPOD) weighted spaces, and (b) generate points given the generating vector or matrices. Armed with this software you will be able to attack your own problems in no time. This talk is based upon the results of collaborations with many colleagues.
This paper is a contemporary review of QMC (‘quasi-Monte Carlo’) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1] s , where s may be large, or even infinite. After a general introduction, the paper surveys recent developments in lattice methods, digital nets, and related themes. Among those recent developments are methods of construction of both lattices and digital nets, to yield QMC rules that have a prescribed rate of convergence for sufficiently smooth functions, and ideally also guaranteed slow growth (or no growth) of the worst-case error as s increases. A crucial role is played by parameters called ‘weights’, since a careful use of the weight parameters is needed to ensure that the worst-case errors in an appropriately weighted function space are bounded, or grow only slowly, as the dimension s increases. Important tools for the analysis are weighted function spaces, reproducing kernel Hilbert spaces, and discrepancy, all of which are discussed with an appropriate level of detail.