Multilevel quasi Monte Carlo methods for elliptic PDEs with random field coefficients via fast white noise sampling

When solving partial differential equations (PDEs) with random fields as coefficients, the efficient sampling of random field realizations can be challenging. In this paper we focus on the fast sampling of Gaussian fields using quasi-random points in a finite element and multilevel quasi Monte Carlo (MLQMC) setting. Our method uses the stochastic PDE (SPDE) approach of Lindgren et al. combined with a new fast algorithm for white noise sampling which is tailored to (ML)QMC. We express white noise as a wavelet series expansion that we divide into two parts. The first part is sampled using quasi-random points and contains a finite number of terms in order of decaying importance to ensure good quasi Monte Carlo (QMC) convergence. The second part is a correction term which is sampled using standard pseudo-random numbers. We show how the sampling of both terms can be performed in linear time and memory complexity in the number of mesh cells via a supermesh construction, yielding an overall linear cost. Furthermore, our technique can be used to enforce the MLQMC coupling even in the case of nonnested mesh hierarchies. We demonstrate the efficacy of our method with numerical experiments.