View abstract

Session III.5 - Information-Based Complexity

Tuesday, June 20, 18:00 ~ 18:30

Multilevel Function Approximation

Mike Giles

University of Oxford, United Kingdom   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

Building on prior research by others on classical and sparse grid interpolation and Multilevel Monte Carlo methods, this seminar will present new ideas on the approximation of parametric functions of the form $f(\theta)$ where $\theta$ is multi-dimensional and each function evaluation corresponds to either a functional of the solution of a PDE, with parametric dependence on $\theta$, or the expected value of a functional of the solution of an SDE, again with a parametric dependence on $\theta$. In both cases, exact sampling of $f(\theta)$ is not possible, and greater accuracy comes at a higher computational cost.

The key idea to improve the computational cost for a given accuracy is a multilevel representation of the function $f(\theta)$ with coarse levels using very accurate approximations of $f(\theta)$ at a very limited number of points, whereas fine levels use inaccurate approximations at a large number of points.

The talk will outline the underpinning literature, and the central idea, together with meta-theorems which determine the computational complexity if certain assumptions are satisfied. On-going research is aimed at the numerical analysis required to determine whether those assumptions are indeed satisfied, as well as computational work to demonstrate the benefits for both PDEs and SDEs, and verify the predicted complexity.


H.-J. Bungartz, M. Griebel. 'Sparse grids'. pp.147-269, Acta Numerica, 2004.

A.-L. Haji-Ali, F. Nobile, R. Tempone. 'Multi-index Monte Carlo: when sparsity meets sampling'. Numerische Mathematik, 132:767-806, 2016.

S. Heinrich. 'Multilevel Monte Carlo methods'. Lecture Notes in Computer Science, 2179:58-67, 2001.

R. Tempone, S. Wolfers. 'Smolyak’s algorithm: a powerful black box for the acceleration of scientific computations'. pp.201-228 in Sparse Grids and Applications, Springer, 2018.

Joint work with Filippo De Angelis (University of Oxford, U.K.) and Christoph Reisinger (University of Oxford, U.K.).

View abstract PDF