A reduced fast component-by-component construction of lattice points for integration in weighted spaces with fast decreasing weights

DOI10.1016/J.CAM.2014.08.017MaRDI QIDQ458162zbMATH OpenOpenAlexFDO

Authors Josef Dick, Peter Kritzer, Gunther Leobacher, Friedrich Pillichshammer

Publication date 7 October 2014

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

numerical integrationquasi-Monte Carlo methodsnumerical resultquadrature rulescomponent-by-component algorithmpolynomial lattice rulesweighted reproducing kernel Hilbert spaces

Mathematics Subject Classification ID

Monte Carlo methods (65C05)

Abstract: Lattice rules and polynomial lattice rules are quadrature rules for approximating integrals over the $s$-dimensional unit cube. Since no explicit constructions of such quadrature methods are known for dimensions $s>2$, one usually has to resort to computer search algorithms. The fast component-by-component approach is a useful algorithm for finding suitable quadrature rules. We present a modification of the fast component-by-component algorithm which yields savings of the construction cost for (polynomial) lattice rules in weighted function spaces. The idea is to reduce the size of the search space for coordinates which are associated with small weights and are therefore of less importance to the overall error compared to coordinates associated with large weights. We analyze tractability conditions of the resulting QMC rules. Numerical results demonstrate the effectiveness of our method.

Recommendations

• Component-by-component digit-by-digit construction of good polynomial lattice rules in weighted Walsh spaces
• On a reduced component-by-component digit-by-digit construction of lattice point sets
• Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
• On the step-by-step construction of quasi--Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces
• Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points

Cites work

• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 3572307 (Why is no real title available?)
• scientific article; zbMATH DE number 2051209 (Why is no real title available?)
• scientific article; zbMATH DE number 914714 (Why is no real title available?)
• A generalized discrepancy and quadrature error bound
• Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces
• Constructing Randomly Shifted Lattice Rules in Weighted Sobolev Spaces
• Construction algorithms for polynomial lattice rules for multivariate 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 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
• Integration and approximation in arbitrary dimensions
• Lattice rules for nonperiodic smooth integrands
• Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces
• On the convergence rate of the component-by-component construction of good lattice rules
• Polynomial lattice point sets
• Theory of Reproducing Kernels
• Tractability of multivariate integration for weighted Korobov classes
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?

Cited in

(13)

• Fast component-by-component construction of lattice algorithms for multivariate approximation with POD and SPOD weights
• Very low truncation dimension for high dimensional integration under modest error demand
• Constructing QMC Finite Element Methods for Elliptic PDEs with Random Coefficients by a Reduced CBC Construction
• Numerical integration in log-Korobov and log-cosine spaces
• On a projection-corrected component-by-component construction
• On a reduced component-by-component digit-by-digit construction of lattice point sets
• Constructing Embedded Lattice Rules for Multivariate Integration
• On combined component-by-component constructions of lattice point sets
• Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness
• Constructing lattice points for numerical integration by a reduced fast successive coordinate search algorithm
• A note on concatenation of quasi-Monte Carlo and plain Monte Carlo rules in high dimensions
• The fast reduced QMC matrix-vector product
• Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces

This page was built for publication: A reduced fast component-by-component construction of lattice points for integration in weighted spaces with fast decreasing weights

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