On Weak Tractability of the Clenshaw-Curtis Smolyak Algorithm

Abstract

We consider the problem of integration of d-variate analytic functions defined on the unit cube with directional derivatives of all orders bounded by 1. We prove that the Clenshaw Curtis Smolyak algorithm leads to weak tractability of the problem. This seems to be the first positive tractability result for the Smolyak algorithm for a normalized and unweighted problem. The space of integrands is not a tensor product space and therefore we have to develop a different proof technique. We use the polynomial exactness of the algorithm as well as an explicit bound on the operator norm of the algorithm.

18 pages

References in corpus (1)

• The Curse of Dimensionality for Numerical Integration of Smooth Functions II

Cited by in corpus (5)

• The role of Frolov's cubature formula for functions with bounded mixed derivative
• Exponential tractability of $L_2$-approximation with function values
• Approximation of Functions: Optimal Sampling and Complexity
• Notes on $(s,t)$-weak tractability: A refined classification of problems with (sub)exponential information complexity
• Some Results on the Complexity of Numerical Integration