Seminar in Numerical Analysis: Robert Scheichl (Heidelberg University)

Multigrid Monte Carlo revisited: fast inference in high dimensions

The fast simulation of Gaussian random fields (GRFs) plays a pivotal role in many research areas such as uncertainty quantification, data science and spatial statistics. In theory, it is a well understood and solved problem, but in practice the efficiency and performance of traditional sampling procedures degenerates quickly when the random field is discretised on a grid with spatial resolution going to zero. Most existing algorithms, such as Cholesky factorisation samplers, do not scale well on large-scale parallel computers. On the other hand, stationary, iterative approaches such as the Gibbs sampler become extremely inefficient at high grid resolution. Already in the late 1980s, Goodman, Sokal and their collaborators wrote a series of papers aimed at accelerating the Gibbs sampler using multigrid ideas. The key observation is the intricate connection of random samplers, such as the Gibbs method, with iterative solvers for linear systems. They proposed the so-called multigrid Monte Carlo (MGMC) method - a random analogue of the multigrid method for solving discretised PDEs. We revisit the MGMC algorithm and provide rigorous theoretical justifications for the optimal scalability of the method for large scale problems, with a cost growing linearly with problem size. Most importantly we extend the method and the analysis to the Bayesian setting, i.e., GRFs conditioned on noisy data. By using bespoke, conditioned variants of the Gibbs sampler on each level of the multigrid hierarchy we are able to sample directly from the posterior with a fixed, grid-independent integrated autocorrelation time. Our theoretical analysis is confirmed by numerical experiments. We further generalise the approach by exploiting more flexible and robust grid hierarchies that were developed in the context of Algebraic Multigrid solvers. Finally, using existing PDE libraries, such as PETSs, the sampler is easily parallelised and scales optimally to large processor numbers.

For further information about the seminar, please visit this webpage.

Export event as iCal