Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

Multivariate integration of infinitely many times differentiable functions in weighted Korobov spaces


Authors: Peter Kritzer, Friedrich Pillichshammer and Henryk Woźniakowski
Journal: Math. Comp. 83 (2014), 1189-1206
MSC (2010): Primary 11K45, 65C05, 65D30
DOI: https://doi.org/10.1090/S0025-5718-2013-02739-1
Published electronically: November 20, 2013
MathSciNet review: 3167455
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study multivariate integration for a weighted Korobov space of periodic infinitely many times differentiable functions for which the Fourier coefficients decay exponentially fast. The weights are defined in terms of two non-decreasing sequences $ \mathbf {a}=\{a_i\}$ and $ \mathbf {b}=\{b_i\}$ of numbers no less than one and a parameter $ \omega \in (0,1)$. Let $ e(n,s)$ be the minimal worst-case error of all algorithms that use $ n$ function values in the $ s$-variate case. We would like to check conditions on $ \mathbf {a}$, $ \mathbf {b}$ and $ \omega $ such that $ e(n,s)$ decays exponentially fast, i.e., for some $ q\in (0,1)$ and $ p>0$ we have $ e(n,s)=\mathcal {O}(q^{\,n^{\,p}})$ as $ n$ goes to infinity. The factor in the $ \mathcal {O}$ notation may depend on $ s$ in an arbitrary way. We prove that exponential convergence holds iff $ B:=\sum _{i=1}^\infty 1/b_i<\infty $ independently of $ \mathbf {a}$ and $ \omega $. Furthermore, the largest $ p$ of exponential convergence is $ 1/B$. We also study exponential convergence with weak, polynomial and strong polynomial tractability. This means that $ e(n,s)\le C(s)\,q^{\,n^{\,p}}$ for all $ n$ and $ s$ and with $ \log \,C(s)=\exp (o(s))$ for weak tractability, with a polynomial bound on $ \log \,C(s)$ for polynomial tractability, and with uniformly bounded $ C(s)$ for strong polynomial tractability. We prove that the notions of weak, polynomial and strong polynomial tractability are equivalent, and hold iff $ B<\infty $ and $ a_i$ are exponentially growing with $ i$. We also prove that the largest (or the supremum of) $ p$ for exponential convergence with strong polynomial tractability belongs to $ [1/(2B),1/B]$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11K45, 65C05, 65D30

Retrieve articles in all journals with MSC (2010): 11K45, 65C05, 65D30


Additional Information

Peter Kritzer
Affiliation: Institut für Finanzmathematik, Johannes Kepler University Linz, Altenbergstraße 69, A-4040 Linz, Austria
Email: peter.kritzer@jku.at

Friedrich Pillichshammer
Affiliation: Institut für Finanzmathematik, Johannes Kepler University Linz, Altenbergstraße 69, A-4040 Linz, Austria
Email: friedrich.pillichshammer@jku.at

Henryk Woźniakowski
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027 – and – Institute of Applied Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland
Email: henryk@cs.columbia.edu

DOI: https://doi.org/10.1090/S0025-5718-2013-02739-1
Received by editor(s): March 9, 2012
Received by editor(s) in revised form: May 23, 2012
Published electronically: November 20, 2013
Additional Notes: The first author was supported by the Austrian Science Fund (FWF), Project P23389-N18.
The second author was partially supported by the Austrian Science Fund (FWF), Project S 9609, that is part of the Austrian Research Network “Analytic Combinatorics and Probabilistic Number Theory”.
The third author was partially supported by the National Science Foundation.
Article copyright: © Copyright 2013 American Mathematical Society