The rate of convergence of sparse grid quadrature on the torus

Abstract

We examine sparse grid quadrature on Korobov spaces; that is, weighted tensor product reproducing kernel Hilbert spaces on the torus. We describe a dimension adaptive quadrature algorithm based on an algorithm of Hegland [ANZIAM J., 44(E):C335, 2003], and also formulate a version of Wasilkowski and Wozniakowski's weighted tensor product algorithm [J. Complexity, 15(3):402, 1999]. We claim that our algorithm is generally lower in cost than Wasilkowski and Wozniakowski's algorithm, and therefore both algorithms have the opti-mal asymptotic rate of convergence given by Theorem 3 of Wasilkowski and Wozniakowski. Even so, if the dimension weights decay slowly enough, both algorithms need a number of points exponential in the dimension to produce a substantial reduction in quadrature error.