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:2208.13610 · Journal of Complexity

A note on the CBC-DBD construction of lattice rules with general positive weights

Peter Kritzer

Published Dec 7, 2022• 1 citation
arXivHTMLPDF
DOI
10.1016/j.jco.2022.101721

Related papers

Construction of good polynomial lattice rules in weighted Walsh spaces by an alternative component-by-component construction

Adrian Ebert, Peter Kritzer, Onyekachi Osisiogu +1 more

arXiv:2101.12586•Mathematics and Computers in Simulation•Sep 14, 2021•0 citations

Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm

Josef Dick, Takashi Goda

arXiv:1912.10651•Journal of Computational and Applied Mathematics•Jun 11, 2020•14 citations

Fast CBC construction of randomly shifted lattice rules achieving O ( n − 1 + δ ) convergence for unbounded integrands over R s in weighted spaces with POD weights

James Nichols, Frances Y. Kuo

Journal of Complexity•Feb 11, 2014•50 citations

Exact results on a general lattice statistical model

Fa Yueh Wu

Solid State Communications•Jan 1, 1972•21 citations

QUASI-MONTE CARLO METHODS FOR HIGH-DIMENSIONAL INTEGRATION: THE STANDARD (WEIGHTED HILBERT SPACE) SETTING AND BEYOND

Frances Y. Kuo, Christoph Schwab, Ian H. Sloan

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.

ANZIAM Journal•Jul 1, 2011•87 citations

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
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 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.