Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules

DOI10.1007/S11075-011-9497-YzbMATH Open1244.65002arXiv1105.2599OpenAlexW2152162686MaRDI QIDQ664602FDOQ664602

Authors: Jan Baldeaux, Josef Dick, Dirk Nuyens, Friedrich Pillichshammer, Gunther Leobacher 

Publication date: 2 March 2012

Published in: Numerical Algorithms (Search for Journal in Brave)

Abstract: We show how to obtain a fast component-by-component construction algorithm for higher order polynomial lattice rules. Such rules are useful for multivariate quadrature of high-dimensional smooth functions over the unit cube as they achieve the near optimal order of convergence. The main problem addressed in this paper is to find an efficient way of computing the worst-case error. A general algorithm is presented and explicit expressions for base~2 are given. To obtain an efficient component-by-component construction algorithm we exploit the structure of the underlying cyclic group. We compare our new higher order multivariate quadrature rules to existing quadrature rules based on higher order digital nets by computing their worst-case error. These numerical results show that the higher order polynomial lattice rules improve upon the known constructions of quasi-Monte Carlo rules based on higher order digital nets.

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

Recommendations

• Construction algorithms for higher order polynomial lattice rules
• Constructing good higher order polynomial lattice rules with modulus of reduced degree
• Construction algorithms for polynomial lattice rules for multivariate integration
• Component-by-component digit-by-digit construction of good polynomial lattice rules in weighted Walsh spaces
• Computational higher order quasi-Monte Carlo integration

zbMATH Keywords

numerical examplesnumerical integrationquasi-Monte Carlo methodsalgorithmdigital netscomponent-by-component constructionworst-case error\(s-\)dimensional netsFourier-Walsh coefficientshigher order polynomial lattice rulesKorobov space

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Well-distributed sequences and other variations (11K36) Pseudo-random numbers; Monte Carlo methods (11K45)

Cites Work

• Title not available (Why is that?)
• Monte Carlo Variance of Scrambled Net Quadrature
• Title not available (Why is that?)
• Explicit Constructions of Quasi-Monte Carlo Rules for the Numerical Integration of High-Dimensional Periodic Functions
• Walsh Spaces Containing Smooth Functions and Quasi–Monte Carlo Rules of Arbitrary High Order
• The decay of the Walsh coefficients of smooth functions
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
• Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules
• A lower estimate for the error of quadrature formulae for certain classes of functions
• QMC rules of arbitrary high order: Reproducing kernel Hilbert space approach
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Construction algorithms for polynomial lattice rules for multivariate integration
• Fast component-by-component construction, a reprise for different kernels
• Construction algorithms for higher order polynomial lattice rules
• On the existence of higher order polynomial lattices based on a generalized figure of merit
• Fast Fourier transform and convolution algorithms
• Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands
• Optimal Polynomials for (T,M,S)-Nets and Numerical Integration of Multivariate Walsh Series
• Primitive Binary Polynomials
• Title not available (Why is that?)
• Constructions of copy rules

Cited In (33)

• Walsh figure of merit for digital nets: an easy measure for higher order convergent QMC
• Construction algorithms for polynomial lattice rules for multivariate integration
• A construction of polynomial lattice rules with small gain coefficients
• Constructions of general polynomial lattices for multivariate integration
• Fast CBC construction of randomly shifted lattice rules achieving \(\mathcal{O}(n^{- 1 + \delta})\) convergence for unbounded integrands over \(\mathbb{R}^s\) in weighted spaces with POD weights
• A Tool for Custom Construction of QMC and RQMC Point Sets
• Fast construction of higher order digital nets for numerical integration in weighted Sobolev spaces
• Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration
• Richardson extrapolation of polynomial lattice rules
• Digital nets with infinite digit expansions and construction of folded digital nets for quasi-Monte Carlo integration
• Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces
• Fast component-by-component construction of lattice algorithms for multivariate approximation with POD and SPOD weights
• Constructing good higher order polynomial lattice rules with modulus of reduced degree
• Extrapolated polynomial lattice rule integration in computational uncertainty quantification
• On the convergence rate of the component-by-component construction of good lattice rules
• Computational higher order quasi-Monte Carlo integration
• Construction-free median quasi-Monte Carlo rules for function spaces with unspecified smoothness and general weights
• A Universal Median Quasi-Monte Carlo Integration
• MDFEM: multivariate decomposition finite element method for elliptic PDEs with uniform random diffusion coefficients using higher-order QMC and FEM
• On the component by component construction of polynomial lattice point sets for numerical integration in weighted Sobolev spaces
• Component-by-component digit-by-digit construction of good polynomial lattice rules in weighted Walsh spaces
• Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation
• Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence
• Construction algorithms for higher order polynomial lattice rules
• A computable figure of merit for quasi-Monte Carlo point sets
• Discrepancy theory and quasi-Monte Carlo integration
• The tent transformation can improve the convergence rate of quasi-Monte Carlo algorithms using digital nets
• Walsh Spaces Containing Smooth Functions and Quasi–Monte Carlo Rules of Arbitrary High Order
• Weighted compound integration rules with higher order convergence for all \(N\)
• Some results on the complexity of numerical integration
• Construction of interlaced scrambled polynomial lattice rules of arbitrary high order
• Approximation of quasi-Monte Carlo worst case error in weighted spaces of infinitely times smooth functions
• MDFEM: multivariate decomposition finite element method for elliptic PDEs with lognormal diffusion coefficients using higher-order QMC and FEM

This page was built for publication: Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules

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