TY - JOUR

T1 - Sparse grid quadrature on products of spheres

AU - Hegland, Markus

AU - Leopardi, Paul

N1 - Publisher Copyright:
© 2015, Springer Science+Business Media New York.

PY - 2015/11/1

Y1 - 2015/11/1

N2 - We examine sparse grid quadrature on weighted tensor products (wtp) of reproducing kernel Hilbert spaces on products of the unit sphere S2, in the case of worst case quadrature error for rules with arbitrary quadrature weights. We describe a dimension adaptive quadrature algorithm based on an algorithm of Hegland (ANZIAM J. 44 (E), C335–C353, 2003), and also formulate an adaptation of Wasilkowski and Woźniakowski’s wtp algorithm (Wasilkowski and Woźniakowski: J. Complex. 15(3), 402–447, 1999), here called the ww algorithm. We prove that the dimension adaptive algorithm is optimal in the sense of Dantzig (Oper. Res. 5(2), 266–2777, 1957) and therefore no greater in cost than the ww algorithm. Both algorithms therefore have the optimal asymptotic rate of convergence of quadrature error given by Theorem 3 of Wasilkowski and Woźniakowski (J. Complex. 15(3), 402–447, 1999). A numerical example shows that, even though the asymptotic convergence rate is optimal, if the dimension weights decay slowly enough, and the dimensionality of the problem is large enough, the initial convergence of the dimension adaptive algorithm can be slow.

AB - We examine sparse grid quadrature on weighted tensor products (wtp) of reproducing kernel Hilbert spaces on products of the unit sphere S2, in the case of worst case quadrature error for rules with arbitrary quadrature weights. We describe a dimension adaptive quadrature algorithm based on an algorithm of Hegland (ANZIAM J. 44 (E), C335–C353, 2003), and also formulate an adaptation of Wasilkowski and Woźniakowski’s wtp algorithm (Wasilkowski and Woźniakowski: J. Complex. 15(3), 402–447, 1999), here called the ww algorithm. We prove that the dimension adaptive algorithm is optimal in the sense of Dantzig (Oper. Res. 5(2), 266–2777, 1957) and therefore no greater in cost than the ww algorithm. Both algorithms therefore have the optimal asymptotic rate of convergence of quadrature error given by Theorem 3 of Wasilkowski and Woźniakowski (J. Complex. 15(3), 402–447, 1999). A numerical example shows that, even though the asymptotic convergence rate is optimal, if the dimension weights decay slowly enough, and the dimensionality of the problem is large enough, the initial convergence of the dimension adaptive algorithm can be slow.

KW - Knapsack problems

KW - Quadrature

KW - Reproducing kernel Hilbert spaces

KW - Sparse grids

KW - Spherical designs

KW - Tractability

UR - http://www.scopus.com/inward/record.url?scp=84945460873&partnerID=8YFLogxK

U2 - 10.1007/s11075-015-9958-9

DO - 10.1007/s11075-015-9958-9

M3 - Article

SN - 1017-1398

VL - 70

SP - 485

EP - 517

JO - Numerical Algorithms

JF - Numerical Algorithms

IS - 3

ER -