WAFOM over abelian groups for quasi-Monte Carlo point sets

DOI10.32917/HMJ/1448323769MaRDI QIDQ906594zbMATH OpenOpenAlexWikidataFDO

Authors Kosuke Suzuki

Publication date 22 January 2016

Published in Hiroshima Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.7276, https://projecteuclid.org/euclid.hmj/1448323769

zbMATH Keywords

numerical integrationquasi-Monte Carlodigital netDick weightMacWilliams-type identityWAFOM

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical integration (65D30) Irregularities of distribution, discrepancy (11K38) Pseudo-random numbers; Monte Carlo methods (11K45)

Abstract: In this paper, we study quasi-Monte Carlo (QMC) rules for numerical integration. J. Dick proved a Koksma-Hlawka type inequality for $alpha$-smooth integrands and gave an explicit construction of QMC rules achieving the optimal rate of convergence in that function class. From this inequality, Matsumoto et al. introduced Walsh figure of merit (WAFOM) $mathrmWAFOM(P)$ for an $mathbb{F}_2$-digital net $P$ as a quickly computable quality criterion for $P$ as a QMC point set. The key ingredient for obtaining WAFOM is the Dick weight, a generalization of the Hamming weight and the Niederreiter-Rosenbloom-Tsfasman (NRT) weight. We extend the notions of the Dick weight and WAFOM for digital nets over a general finite abelian group $G$, and show that this version of WAFOM satisfies Koksma-Hlawka type inequality when $G$ is cyclic. We give a MacWilliams-type identity on the weight enumerator polynomials for the Dick weight, by which we can compute the minimum Dick weight as well as WAFOM. We give a lower bound of WAFOM of order $N^{-C{\text{'}}_G(logN)/s}$ and an upper bound of lowest WAFOM of order $N^{-C_G(logN)/s}$ for given $(G,N,s)$ if $(logN)/s$ is sufficiently large, where $N$ is the cardinality of the point set $P$, $P$ is a quadrature rule in $[0,1{)}^s$, and $C{\text{'}}_G$ and $C_G$ are constants depending only on the cardinality of $G$. These bounds generalize the bounds given by Yoshiki and others given for $G=mathbb{F}_2$.

Recommendations

• Quasi-Monte Carlo point sets with small t-values and WAFOM
• A distance measure on finite abelian groups and an application to quasi-Monte Carlo integration
• A computable figure of merit for quasi-Monte Carlo point sets
• Monte Carlo circuits for the abelian permutation group intersection problem
• A search for extensible low-WAFOM point sets
• On an example of finite hybrid quasi-Monte Carlo point sets
• Probabilistic discrepancy bound for Monte Carlo point sets
• Fast Monte Carlo algorithms for permutation groups
• Quasi-Monte-Carlo methods and the dispersion of point sequences

Cited in

(12)

• Existence of higher order convergent quasi-Monte Carlo rules via Walsh figure of merit
• Walsh figure of merit for digital nets: an easy measure for higher order convergent QMC
• The mean square quasi-Monte Carlo error for digitally shifted digital nets
• A lower bound on WAFOM
• An explicit construction of point sets with large minimum Dick weight
• A Universal Median Quasi-Monte Carlo Integration
• A search for extensible low-WAFOM point sets
• A distance measure on finite abelian groups and an application to quasi-Monte Carlo integration
• Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions
• A computable figure of merit for quasi-Monte Carlo point sets
• Construction of interlaced polynomial lattice rules for infinitely differentiable functions
• Approximation of quasi-Monte Carlo worst case error in weighted spaces of infinitely times smooth functions

This page was built for publication: WAFOM over abelian groups for quasi-Monte Carlo point sets

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