A practical Multilevel quasi-Monte Carlo method for simulating elliptic PDEs with random coefficients

The efficient numerical simulation of models described by partial differential equations (PDEs) is an important task in engineering and science. Often, the coefficients in such models are not known exactly or are subject to uncertainty. Because the uncertainty propagates through the solution, this typically leads to very high dimensional quadrature problems when computing the statistics of certain quantities of interest. Recently, the Multilevel Monte Carlo method (MLMC), a combination of Monte Carlo sampling and a multigrid idea, has been successfully applied to these problems, showing significant gains. In this presentation, we investigate how the classical MLMC method can be improved even further by combining it with quasi-Monte Carlo (QMC) integration. Specifically, we introduce a Multilevel quasi-Monte Carlo estimator (MLQMC) based on randomized rank-1 lattice rules. The error analysis of this estimator results in an optimal number of samples at each level that is a significant improvement over the classical amount of work. Numerical results illustrate the superiority of the new MLQMC method over the standard MLMC estimator. We show that for certain problems, one can achieve a cost almost inversely proportional to the requested tolerance on the root-mean-square error. This is much better than the classical method, for which the cost is inversely proportional to the square of the requested tolerance.status: publishe