Construction of interlaced polynomial lattice rules for infinitely differentiable functions

DOI10.1007/S00211-017-0882-XzbMATH Open1385.65002arXiv1602.00793OpenAlexW2263105604MaRDI QIDQ2408931FDOQ2408931

Takashi Goda, Kosuke Suzuki, Josef Dick, Takehito Yoshiki

Publication date: 10 October 2017

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

Abstract: We study multivariate integration over the $s$-dimensional unit cube in a weighted space of infinitely differentiable functions. It is known from a recent result by Suzuki that there exists a good quasi-Monte Carlo (QMC) rule which achieves a super-polynomial convergence of the worst-case error in this function space, and moreover, that this convergence behavior is independent of the dimension under a certain condition on the weights. In this paper we provide a constructive approach to finding a good QMC rule achieving such a dimension-independent super-polynomial convergence of the worst-case error. Specifically, we prove that interlaced polynomial lattice rules, with an interlacing factor chosen properly depending on the number of points $N$ and the weights, can be constructed using a fast component-by-component algorithm in at most $O(sN(logN{)}^2)$ arithmetic operations to achieve a dimension-independent super-polynomial convergence. The key idea for the proof of the worst-case error bound is to use a variant of Jensen's inequality with a purposely-designed concave function.

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

zbMATH Keywords

convergencenumerical experimentsfast Fourier transformWalsh functionsmultivariate integrationworst-case errorquasi-Monte Carlo algorithmcomponent-by-component construction of lattice point setsfast component-by-component algorithmInterlaced polynomial lattice rulesweighted function space of infinitely differentiable functions

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Random number generation in numerical analysis (65C10) Probabilistic models, generic numerical methods in probability and statistics (65C20) Numerical quadrature and cubature formulas (65D32) Numerical methods for discrete and fast Fourier transforms (65T50)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bounds on Walsh coefficients by dyadic difference and a new Koksma-Hlawka type inequality for quasi-Monte Carlo integration
• Formulas for the Walsh coefficients of smooth functions and their application to bounds on the Walsh coefficients
• A class of generalized Walsh functions
• 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
• Integration in Hermite spaces of analytic functions
• Lattice rules for nonperiodic smooth integrands
• Exponential convergence and tractability of multivariate integration for Korobov spaces
• Low-discrepancy point sets obtained by digital constructions over finite fields
• Multivariate integration of infinitely many times differentiable functions in weighted Korobov spaces
• Higher Order QMC Petrov--Galerkin Discretization for Affine Parametric Operator Equations with Random Field Inputs
• Hyperbolic cross approximation in infinite dimensions
• Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
• Codes for the \(m\)-metric
• Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions
• A computable figure of merit for quasi-Monte Carlo point sets
• WAFOM over abelian groups for quasi-Monte Carlo point sets
• Polynomial Lattice Point Sets
• Low-discrepancy point sets
• Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces
• Construction of interlaced scrambled polynomial lattice rules of arbitrary high order
• Random weights, robust lattice rules and the geometry of the \(cbcrc\) algorithm
• Proof techniques in quasi-Monte Carlo theory
• Fast construction of higher order digital nets for numerical integration in weighted Sobolev spaces

Cited In (4)

• Super-polynomial accuracy of one dimensional randomized nets using the median of means
• A Universal Median Quasi-Monte Carlo Integration
• Efficient multivariate approximation on the cube
• Approximation of quasi-Monte Carlo worst case error in weighted spaces of infinitely times smooth functions

Recommendations

• Title not available (Why is that?) 👍 👎
• Interpolation lattices for hyperbolic cross trigonometric polynomials 👍 👎
• Construction algorithms for polynomial lattice rules for multivariate integration 👍 👎
• Constructions of general polynomial lattices for multivariate integration 👍 👎
• Polynomial Interpolation in Several Variables: Lattices, Differences, and Ideals 👍 👎
• Scrambled Polynomial Lattice Rules for Infinite-Dimensional Integration 👍 👎
• Construction algorithms for higher order polynomial lattice rules 👍 👎
• Interpolation lattices in several variables 👍 👎
• Interpolation by lattice polynomial functions: a polynomial time algorithm 👍 👎
• General Interpolation by Polynomial Functions of Distributive Lattices 👍 👎

This page was built for publication: Construction of interlaced polynomial lattice rules for infinitely differentiable functions

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