A construction of polynomial lattice rules with small gain coefficients

DOI10.1007/S00211-011-0385-0zbMATH Open1298.65010arXiv1003.4785OpenAlexW1988921022MaRDI QIDQ644778FDOQ644778

Authors: Jan Baldeaux, Josef Dick 

Publication date: 7 November 2011

Published in: Numerische Mathematik (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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

Uses Software

• Algorithm 823
• TOMS659
• sobol.cc

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)