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 optimal 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. References

• B. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge University Press, Cambridge, 1990.
• T. Gerstner and M. Griebel. Dimension-adaptive tensor product quadrature. Computing, 71:65--87, 2003. doi:10.1007/s00607-003-0015-5
• M. Hegland. Adaptive sparse grids. ANZIAM Journal, 44 (E):C335--C353, 2003. http://anziamj.austms.org.au/ojs/index.php/ANZIAMJ/article/view/685
• F. J. Hickernell and H. Wozniakowski. Tractability of multivariate integration for periodic functions. Journal of Complexity, 17(4):660--682, 2001. doi:10.1006/jcom.2001.0592
• N. M. Korobov. Approximate evaluation of repeated integrals. {(Russian)}. Doklady Akademii Nauk SSSR, 124(6):1207--1210, 1959.
• N. M. Korobov. Computation of multiple integrals by the method of optimal coefficients. {(Russian)}. Vestnik Moskov. Univ. Ser. Mat. Meh. Astr. Fiz. Him., (4):19--25, 1959.
• F. Y. Kuo and I. H. Sloan. {Quasi-Monte Carlo} methods can be efficient for integration over products of spheres. Journal of Complexity, 21(2):196--210, 2005. doi:10.1016/j.jco.2004.07.0015
• I. H. Sloan and H. Wozniakowski. Tractability of multivariate integration for weighted {Korobov} classes. Journal of Complexity, 17(4):697--721, 2001. doi:10.1006/jcom.2001.0599
• S. A. Smolyak. Quadrature and interpolation formulas for tensor products of certain classes of functions. Dokl. Akad. Nauk SSSR, 4:240--243, 1963.
• G. W. Wasilkowski and H. Wozniakowski. Weighted tensor product algorithms for linear multivariate problems. Journal of Complexity, 15(3):402--447, 1999. doi:10.1006/jcom.1999.0512