Component-by-component digit-by-digit construction of good polynomial lattice rules in weighted Walsh spaces

DOI10.1007/S00365-021-09554-1MaRDI QIDQ2165575zbMATH OpenOpenAlexFDO

Authors Adrian Ebert, Peter Kritzer, Onyekachi Osisiogu, Tetiana A. Stepaniuk

Publication date 20 August 2022

Published in Constructive Approximation (Search for Journal in Brave)

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

zbMATH Keywords

component-by-component constructiondigit-by-digit constructionfast implementationsnumerical integrationpolynomial lattice pointsquasi-Monte Carlo methodsweighted function spaces

Mathematics Subject Classification ID

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

Abstract: We consider the efficient construction of polynomial lattice rules, which are special cases of so-called quasi-Monte Carlo (QMC) rules. These are of particular interest for the approximate computation of multivariate integrals where the dimension $d$ may be in the hundreds or thousands. We study a construction method that assembles the generating vector, which is in this case a vector of polynomials over a finite field, of the polynomial lattice rule in a digit-by-digit (or, equivalently, coefficient-by-coefficient) fashion. As we will show, the integration error of the corresponding QMC rules achieves excellent convergence order, and, under suitable conditions, we can vanquish the curse of dimensionality by considering function spaces equipped with coordinate weights. The construction algorithm is based on a quality measure that is independent of the underlying smoothness of the function space and can be implemented in a fast manner (without the use of fast Fourier transformations). Furthermore, we illustrate our findings with extensive numerical results.

Recommendations

• Construction of good polynomial lattice rules in weighted Walsh spaces by an alternative component-by-component construction
• Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces
• Constructions of general polynomial lattice rules based on the weighted star discrepancy
• Component-by-component construction of good lattice rules with a composite number of points
• The construction of extensible polynomial lattice rules with small weighted star discrepancy
• On the component by component construction of polynomial lattice point sets for numerical integration in weighted Sobolev spaces
• Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules
• Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm
• A construction of polynomial lattice rules with small gain coefficients
• Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness

Cites work

• Component-by-component construction of good lattice rules
• Construction algorithms for polynomial lattice rules for multivariate integration
• Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness
• Discrepancy theory and quasi-Monte Carlo integration
• Factoring Finite Factor Rings
• 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
• High-dimensional integration: The quasi-Monte Carlo way
• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• 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 53679 (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?)
• Low-discrepancy point sets obtained by digital constructions over finite fields
• Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces
• Point sets and sequences with small discrepancy
• Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm
• The existence of good extensible rank-1 lattices
• 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

(10)

• Constructing good higher order polynomial lattice rules with modulus of reduced degree
• Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces
• Construction of good polynomial lattice rules in weighted Walsh spaces by an alternative component-by-component construction
• On the component by component construction of polynomial lattice point sets for numerical integration in weighted Sobolev spaces
• Quasi-Monte Carlo methods for high-dimensional integration: the standard (weighted Hilbert space) setting and beyond
• A reduced fast component-by-component construction of lattice points for integration in weighted spaces with fast decreasing weights
• Construction algorithms for polynomial lattice rules for multivariate integration
• Construction algorithms for higher order polynomial lattice rules
• Constructions of general polynomial lattices for multivariate integration
• Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules

This page was built for publication: Component-by-component digit-by-digit construction of good polynomial lattice rules in weighted Walsh spaces

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