FoCM 2014 conference
Workshop B5 - Information Based Complexity - Semi-plenary talk
December 17, 17:05 ~ 17:55 - Room B23
Integration problems with a large or infinite number of variables
Michael Gnewuch
Christian Albrechts University Kiel, Germany - mig@informatik.uni-kiel.de
The evaluation of integrals of functions with a large or even infinite number of variables is an important task in physics, quantum chemistry and quantitative finance. If one, for instance, wants to compute the expectation of a funtional of a stochastic process, then employing a suitable series expansion of the stochastic process the problem can be transformed into the problem of calculating the integral of a function of infinitely many variables.
For the moment let us focus on infinite-dimensional integration. A valuable technique to tackle the integration problem is to use a function decomposition -- the integrand is represented as an infinite sum of functions of finitely many variables. Cleverly designed algorithms, such as multilevel algorithms or multivariate decomposition methods, deal with a finite number of important summands. They balance the computational burden spent on the corresponding finite-dimensional integration sub-problems in order to minimize the computational cost for achieving a given error tolerance.
Important function decompositions are, e.g., the well-known ANOVA ("Analysis of Variance'') decomposition or anchored decompositions.
It turns out one function decomposition may be more convenient for error analysis while another is more convenient for the actual design of competitive algorithms. An example is the approximation of certain classes of integrands of infinitely many variables by randomized algorithms: On the one hand the ANOVA decomposition is a valuable tool for the error analysis, but even the explicit computation of the ANOVA components of low order is infeasible (in the sense that it is more expensive than the original integration problem). On the other hand, the components of anchored decompositions can be computed efficiently and therefore they can be used to design algorithms, but the direct error analysis may be complicated.
In this talk we present optimal results for high- and infinite-dimensional integration. In some settings (depending on the class of integrands we consider, the class of algorithms we admit and the way we account for the computational cost) one can derive these results directly, and we will see situations were the results can be transfered to other settings.
Joint work with Jan Baldeaux (UTS Sydney, Australia), Josef Dick (UNSW Sydney, Australia), Mario Hefter (TU Kaiserslautern, Germany), Aicke Hinrichs (JKU Linz, Austria), and Klaus Ritter (TU Kaiserslautern, Germany).