Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



The curse of dimensionality for numerical integration of smooth functions

Authors: A. Hinrichs, E. Novak, M. Ullrich and H. Woźniakowski
Journal: Math. Comp. 83 (2014), 2853-2863
MSC (2010): Primary 65D30, 65Y20, 41A63, 41A55
Published electronically: June 20, 2014
MathSciNet review: 3246812
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We prove the curse of dimensionality for multivariate integration of $ C^r$ functions: The number of needed function values to achieve an error $ \epsilon $ is larger than $ c_r (1+\gamma )^d$ for $ \epsilon \le \epsilon _0$, where $ c_r,\gamma >0$. The proofs are based on volume estimates for $ r=1$ together with smoothing by convolution. This allows us to obtain smooth fooling functions for $ r>1$.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65D30, 65Y20, 41A63, 41A55

Retrieve articles in all journals with MSC (2010): 65D30, 65Y20, 41A63, 41A55

Additional Information

A. Hinrichs
Affiliation: Institut für Mathematik, Universität Rostock, Ulmenstraße 69, 18051 Rostock, Germany

E. Novak
Affiliation: Mathematisches Institut, Universität Jena, Ernst-Abbe-Platz 2, 07743 Jena, Germany

M. Ullrich
Affiliation: Dipartimento di Matematica, Università Roma Tre, Largo San Leonardo Murialdo 1, 00146 Roma, Italy

H. 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

Keywords: Curse of dimensionality, numerical integration, high dimensional numerical problems
Received by editor(s): November 5, 2012
Received by editor(s) in revised form: April 16, 2013
Published electronically: June 20, 2014
Additional Notes: The first author was partially supported by the DFG-Priority Program 1324.
The third author was supported by DFG GRK 1523 and ERC Advanced Grant PTRELSS
The fourth author was partially supported by the National Science Foundation
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society