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

DOI10.1007/s11075-011-9497-yzbMath1244.65002arXiv1105.2599MaRDI QIDQ664602

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

Publication date: 2 March 2012

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

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

zbMATH Keywords

algorithm; numerical integration; numerical examples; quasi-Monte Carlo methods; digital nets; worst-case error; component-by-component construction; \(s-\)dimensional nets; Fourier-Walsh coefficients; higher order polynomial lattice rules; Korobov space

Mathematics Subject Classification ID

65C05: Monte Carlo methods

11K36: Well-distributed sequences and other variations

11K45: Pseudo-random numbers; Monte Carlo methods

Related Items

Richardson Extrapolation of Polynomial Lattice Rules, MDFEM: Multivariate decomposition finite element method for elliptic PDEs with lognormal diffusion coefficients using higher-order QMC and FEM, Extrapolated Polynomial Lattice Rule Integration in Computational Uncertainty Quantification, Construction-Free Median Quasi-Monte Carlo Rules for Function Spaces with Unspecified Smoothness and General Weights, Discrepancy Theory and Quasi-Monte Carlo Integration, A computable figure of merit for quasi-Monte Carlo point sets, Digital nets with infinite digit expansions and construction of folded digital nets for quasi-Monte Carlo integration, Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence, Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation, Construction algorithms for higher order polynomial lattice rules, Weighted compound integration rules with higher order convergence for all \(N\), Construction of interlaced scrambled polynomial lattice rules of arbitrary high order, MDFEM: multivariate decomposition finite element method for elliptic PDEs with uniform random diffusion coefficients using higher-order QMC and FEM, 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, Constructing good higher order polynomial lattice rules with modulus of reduced degree, Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces, 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, Walsh Figure of Merit for Digital Nets: An Easy Measure for Higher Order Convergent QMC, Some Results on the Complexity of Numerical Integration

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Construction algorithms for higher order polynomial lattice rules
• Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands
• 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.
• Fast Fourier transform and convolution algorithms
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
• Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces
• Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules
• On the existence of higher order polynomial lattices based on a generalized figure of merit
• 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
• 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
• Monte Carlo Variance of Scrambled Net Quadrature
• Primitive Binary Polynomials
• Optimal Polynomials for (T,M,S)-Nets and Numerical Integration of Multivariate Walsh Series
• Construction algorithms for polynomial lattice rules for multivariate integration
• A lower estimate for the error of quadrature formulae for certain classes of functions
• Constructions of copy rules