Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Multivariate integration for analytic functions with Gaussian kernels


Authors: Frances Y. Kuo, Ian H. Sloan and Henryk Woźniakowski
Journal: Math. Comp. 86 (2017), 829-853
MSC (2010): Primary 41A63, 41A99; Secondary 65D30
DOI: https://doi.org/10.1090/mcom/3144
Published electronically: June 29, 2016
MathSciNet review: 3584550
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study multivariate integration of analytic functions defined on $\mathbb {R}^d$. These functions are assumed to belong to a reproducing kernel Hilbert space whose kernel is Gaussian, with nonincreasing shape parameters. We prove that a tensor product algorithm based on the univariate Gauss-Hermite quadrature rules enjoys exponential convergence and computes an $\varepsilon$-approximation for the $d$-variate integration using an order of $(\ln \varepsilon ^{-1})^d$ function values as $\varepsilon$ goes to zero. We prove that the exponent $d$ is sharp by proving a lower bound on the minimal (worst case) error of any algorithm based on finitely many function values. We also consider four notions of tractability describing how the minimal number $n(\varepsilon ,d)$ of function values needed to find an $\varepsilon$-approximation in the $d$-variate case behaves as a function of $d$ and $\ln \varepsilon ^{-1}$. One of these notions is new. In particular, we prove that for all positive shape parameters, the minimal number $n(\varepsilon ,d)$ is larger than any polynomial in $d$ and $\ln \varepsilon ^{-1}$ as $d$ and $\varepsilon ^{-1}$ go to infinity. However, it is not exponential in $d^{ t}$ and $\ln \varepsilon ^{-1}$ whenever $t>1$.


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

References

Similar Articles

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

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


Additional Information

Frances Y. Kuo
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, New South Wales 2052, Australia
MR Author ID: 703418
Email: f.kuo@unsw.edu.au

Ian H. Sloan
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, New South Wales 2052, Australia
MR Author ID: 163675
ORCID: 0000-0003-3769-0538
Email: i.sloan@unsw.edu.au

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

Received by editor(s): October 9, 2014
Received by editor(s) in revised form: August 5, 2015
Published electronically: June 29, 2016
Article copyright: © Copyright 2016 American Mathematical Society