A construction of polynomial lattice rules with small gain coefficients

DOI10.1007/S00211-011-0385-0MaRDI QIDQ644778zbMATH OpenOpenAlexFDO

Authors Jan Baldeaux, Josef Dick

Publication date 7 November 2011

Published in Numerische Mathematik (Search for Journal in Brave)

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

zbMATH Keywords

quasi-Monte Carlo methodsvariancelower and upper boundscomponent-by-component algorithmpolynomial lattice rulesscramblingdigital \((t,m,s)\)-netsKorobov polynomial lattice rulesworst-case variance

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Random number generation in numerical analysis (65C10) Numerical integration (65D30) Well-distributed sequences and other variations (11K36) Pseudo-random numbers; Monte Carlo methods (11K45) Special sequences (11K31)

Abstract: In this paper we construct polynomial lattice rules which have, in some sense, small gain coefficients using a component-by-component approach. The gain coefficients, as introduced by Owen, indicate to what degree the method improves upon Monte Carlo. We show that the variance of an estimator based on a scrambled polynomial lattice rule constructed component-by-component decays at a rate of $N^{-(2alpha+1)+delta}$, for all $delta>0$, assuming that the function under consideration has bounded fractional variation of order $alpha$ and where $N$ denotes the number of quadrature points. An analogous result is obtained for Korobov polynomial lattice rules. It is also established that these rules are almost optimal for the function space considered in this paper. Furthermore, we discuss the implementation of the component-by-component approach and show how to reduce the computational cost associated with it. Finally, we present numerical results comparing scrambled polynomial lattice rules and scrambled digital nets.

Recommendations

• Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules
• Construction algorithms for polynomial lattice rules for multivariate integration
• Construction of interlaced scrambled polynomial lattice rules of arbitrary high order
• Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm
• Constructions of general polynomial lattices for multivariate integration

Cites work

• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 3153486 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 1321825 (Why is no real title available?)
• scientific article; zbMATH DE number 1790451 (Why is no real title available?)
• scientific article; zbMATH DE number 822320 (Why is no real title available?)
• scientific article; zbMATH DE number 914714 (Why is no real title available?)
• A characterization of higher order nets using Weyl sums and its applications
• Algorithm 823
• Component-by-component construction of good lattice rules
• Construction algorithms for polynomial lattice rules for multivariate integration
• Deterministic and stochastic error bounds in numerical analysis
• 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
• Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence
• Low-discrepancy point sets obtained by digital constructions over finite fields
• Monte Carlo Variance of Scrambled Net Quadrature
• Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces
• On the Numerical Integration of Walsh Series by Number-Theoretic Methods
• On the \(L_2\)-discrepancy for anchored boxes
• On the variance of quadrature over scrambled nets and sequences
• Optimal Polynomials for (T,M,S)-Nets and Numerical Integration of Multivariate Walsh Series
• Optimal quadrature for Haar wavelet spaces
• Point sets and sequences with small discrepancy
• Randomized Polynomial Lattice Rules for Multivariate Integration and Simulation
• Remark on algorithm 659
• Scrambled net variance for integrals of smooth functions
• Strong tractability of integration using scrambled Niederreiter points
• The Mean Square Discrepancy of Scrambled (t,s)-Sequences
• The discrepancy and gain coefficients of scrambled digital nets.
• The price of pessimism for multidimensional quadrature
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?

Cited in

(6)

• Construction of scrambled polynomial lattice rules over \(\mathbb{F}_{2}\) with small mean square weighted \(\mathcal{L}_{2}\) discrepancy
• Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration
• Randomized Polynomial Lattice Rules for Multivariate Integration and Simulation
• Component-by-component digit-by-digit construction of good polynomial lattice rules in weighted Walsh spaces
• The nonzero gain coefficients of Sobol's sequences are always powers of two
• Construction of interlaced scrambled polynomial lattice rules of arbitrary high order

Describes a project that uses

Uses Software

• sobol.cc
• TOMS659
• Algorithm 823

This page was built for publication: A construction of polynomial lattice rules with small gain coefficients

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