Multilevel quasi-Monte Carlo methods for lognormal diffusion problems

In this paper we present a rigorous cost and error analysis of amultilevel estimator based on randomly shifted Quasi-Monte Carlo (QMC)lattice rules for lognormal diffusion problems. These problems are motivatedby uncertainty quantification problems in subsurface flow. We extend the convergenceanalysis in [Graham et al., Numer. Math. 2014] to multilevel QuasiMonteCarlo finite element discretisations and give a constructive proof ofthe dimension-independent convergence of the QMC rules. More precisely, weprovide suitable parameters for the construction of such rules that yield therequired variance reduction for the multilevel scheme to achieve an ε-error witha cost of O(ε−θ) with θ < 2, and in practice even θ ≈ 1, for sufficiently fastdecaying covariance kernels of the underlying Gaussian random field inputs.This confirms that the computational gains due to the application of multilevelsampling methods and the gains due to the application of QMC methods, bothdemonstrated in earlier works for the same model problem, are complementary.A series of numerical experiments confirms these gains. The results showthat in practice the multilevel QMC method consistently outperforms boththe multilevel MC method and the single-level variants even for nonsmoothproblems.