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

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.

References in corpus (3)

• Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order
• Explicit constructions of quasi-Monte Carlo rules for the numerical integration of high dimensional periodic functions
• The decay of the Walsh coefficients of smooth functions

Cited by in corpus (21)

• Higher order QMC Galerkin discretization for parametric operator equations
• Construction of interlaced scrambled polynomial lattice rules of arbitrary high order
• The construction of good lattice rules and polynomial lattice rules
• Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces
• Infinite-Dimensional Integration in Weighted Hilbert Spaces: Anchored Decompositions, Optimal Deterministic Algorithms, and Higher Order Convergence
• Construction-free median quasi-Monte Carlo rules for function spaces with unspecified smoothness and general weights
• Higher order Quasi-Monte Carlo integration for Bayesian Estimation
• Embeddings of Weighted Hilbert Spaces and Applications to Multivariate and Infinite-Dimensional Integration
• Digital nets with infinite digit expansions and construction of folded digital nets for quasi-Monte Carlo integration
• A universal median quasi-Monte Carlo integration
• Richardson extrapolation of polynomial lattice rules
• WAFOM on abelian groups for quasi-Monte Carlo point sets
• MDFEM: Multivariate decomposition finite element method for elliptic PDEs with lognormal diffusion coefficients using higher-order QMC and FEM
• Fast construction of higher order digital nets for numerical integration in weighted Sobolev spaces
• MDFEM: Multivariate decomposition finite element method for elliptic PDEs with uniform random diffusion coefficients using higher-order QMC and FEM
• Constructing good higher order polynomial lattice rules with modulus of reduced degree
• Walsh Figure of Merit for Digital Nets: An Easy Measure for Higher Order Convergent QMC
• Richardson extrapolation allows truncation of higher order digital nets and sequences
• Some Results on the Complexity of Numerical Integration
• Higher order Quasi-Monte Carlo integration for holomorphic, parametric operator equations
• Quasi-Random Physics-informed Neural Networks