Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Infinite-dimensional integration on weighted Hilbert spaces


Author: Michael Gnewuch
Journal: Math. Comp. 81 (2012), 2175-2205
MSC (2010): Primary 65C05, 65D30; Secondary 11K38
Published electronically: April 5, 2012
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the numerical integration problem for functions with infinitely many variables which stem from a weighted reproducing kernel Hilbert space. We study the worst case $ \varepsilon $-complexity which is defined as the minimal cost among all algorithms whose worst case error over the Hilbert space unit ball is at most $ \varepsilon $. Here we assume that the cost of evaluating a function depends polynomially on the number of active variables. The infinite-dimensional integration problem is tractable if the $ \varepsilon $-complexity is bounded by a constant times a power of $ 1/\varepsilon $. The smallest such power is called the exponent of tractability.

We provide improved lower bounds for the exponent of tractability for general finite-order weights and, with the help of multilevel algorithms, improved upper bounds for three newly defined classes of finite-order weights. The newly defined finite-intersection weights model the situation where each group of variables interacts with at most $ \rho $ other groups of variables, $ \rho $ some fixed number. For these weights we obtain sharp upper bounds for any decay of the weights and any polynomial degree of the cost function. For the other two classes of finite-order weights our upper bounds are sharp if, e.g., the decay of the weights is fast or slow enough.

Furthermore, we deduce a lower bound for the exponent of tractability for arbitrary weights and a constructive upper bound for product weights.


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


Similar Articles

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

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


Additional Information

Michael Gnewuch
Affiliation: Department of Computer Science, Columbia University, 1214 Amsterdam Avenue, New York, New York 10027

DOI: http://dx.doi.org/10.1090/S0025-5718-2012-02583-X
PII: S 0025-5718(2012)02583-X
Received by editor(s): May 21, 2010
Received by editor(s) in revised form: May 31, 2011
Published electronically: April 5, 2012
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.