Tractability of multivariate integration for periodic functions

Fred J. Hickernell*, Henryk Woźniakowski

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

29 Citations (Scopus)


We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor e for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in e-1 and d. Strong tractability means that we have only a polynomial dependence in e-1. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γj moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑j=1 γj < ∞, whereas tractability holds iff lim supd→∞j=1 d γj/ln d < ∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity 17 (2001), 388-441) concerning decomposable kernels.

Original languageEnglish
Pages (from-to)660-682
Number of pages23
JournalJournal of Complexity
Issue number4
Publication statusPublished - Dec 2001
Externally publishedYes

Scopus Subject Areas

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • Mathematics(all)
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'Tractability of multivariate integration for periodic functions'. Together they form a unique fingerprint.

Cite this