Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness

DOI10.1016/J.JCO.2021.101555MaRDI QIDQ1979419zbMATH OpenOpenAlexFDO

Authors Adrian Ebert, Peter Kritzer, Dirk Nuyens, Onyekachi Osisiogu

Publication date 2 September 2021

Published in Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

component-by-component constructiondigit-by-digit constructionfast constructionlattice pointsnumerical integrationquasi-Monte Carlo methods

Mathematics Subject Classification ID

Approximate quadratures (41A55) Multidimensional problems (41A63) Monte Carlo methods (65C05) Numerical integration (65D30) Numerical quadrature and cubature formulas (65D32)

Abstract: Lattice rules are among the most prominently studied quasi-Monte Carlo methods to approximate multivariate integrals. A rank-1 lattice rule to approximate an $s$-dimensional integral is fully specified by its generating vector $mathbfzinmathbb{Z}^s$ and its number of points $N$. While there are many results on the existence of "good" rank-1 lattice rules, there are no explicit constructions for good generating vectors for dimensions $sge3$. This is why one usually resorts to computer search algorithms. Motivated by earlier work of Korobov from 1963 and 1982, we present two variants of search algorithms for good lattice rules and show that the resulting rules exhibit a convergence rate in weighted function spaces that can be arbitrarily close to the optimal rate. Moreover, contrary to most other algorithms, we do not need to know the smoothness of our integrands in advance, the generating vector will still recover the convergence rate associated with the smoothness of the particular integrand, and, under appropriate conditions on the weights, the error bounds can be stated without dependence on $s$. The search algorithms presented in this paper are two variants of the well-known component-by-component (CBC) construction, one of which is combined with a digit-by-digit (DBD) construction. We present numerical results for both algorithms using fast construction algorithms in the case of product weights. They confirm our theoretical findings.

Recommendations

• A note on the CBC-DBD construction of lattice rules with general positive weights
• Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm
• Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points
• Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
• Successive coordinate search and component-by-component construction of rank-1 lattice rules

Cites work

• A generalized discrepancy and quadrature error bound
• A reduced fast component-by-component construction of lattice points for integration in weighted spaces with fast decreasing weights
• Component-by-component construction of good lattice rules
• Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces
• Constructing QMC Finite Element Methods for Elliptic PDEs with Random Coefficients by a Reduced CBC Construction
• Construction algorithms for good extensible lattice rules
• Construction of good rank-1 lattice rules based on the weighted star discrepancy
• Efficient Weighted Lattice Rules with Applications to Finance
• Error Bounds for the Method of Good Lattice Points
• Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
• Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points
• Good lattice rules in weighted Korobov spaces with general weights
• High-dimensional integration: The quasi-Monte Carlo way
• scientific article; zbMATH DE number 3145344 (Why is no real title available?)
• scientific article; zbMATH DE number 3878229 (Why is no real title available?)
• scientific article; zbMATH DE number 3728384 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 3591295 (Why is no real title available?)
• scientific article; zbMATH DE number 914714 (Why is no real title available?)
• scientific article; zbMATH DE number 3187192 (Why is no real title available?)
• Introduction to quasi-Monte Carlo integration and applications
• Lattice Rules for Multiple Integration and Discrepancy
• Lattice rules for nonperiodic smooth integrands
• Lattice rules in non-periodic subspaces of Sobolev spaces
• On the convergence rate of the component-by-component construction of good lattice rules
• On the step-by-step construction of quasi--Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces
• Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm
• Successive coordinate search and component-by-component construction of rank-1 lattice rules
• Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions
• The existence of good extensible rank-1 lattices
• Tractability of multivariate integration for weighted Korobov classes
• Tractability of multivariate problems. Volume I: Linear information
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
• Zur angenäherten Berechnung mehrfacher Integrale

Cited in

(13)

• Component-by-component digit-by-digit construction of good polynomial lattice rules in weighted Walsh spaces
• Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm
• Periodization strategy may fail in high dimensions
• Construction of good polynomial lattice rules in weighted Walsh spaces by an alternative component-by-component construction
• A note on the CBC-DBD construction of lattice rules with general positive weights
• Construction-free median quasi-Monte Carlo rules for function spaces with unspecified smoothness and general weights
• Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate
• Constructing Embedded Lattice Rules for Multivariate Integration
• On a reduced component-by-component digit-by-digit construction of lattice point sets
• A Universal Median Quasi-Monte Carlo Integration
• A simple universal algorithm for high-dimensional integration
• Optimal algorithms for numerical integration: recent results and open problems
• Quasi-Monte Carlo integration over \(\mathbb{R}^s\) based on digital nets

This page was built for publication: Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness

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