A Multilevel Stochastic Collocation Method for Partial Differential Equations with Random Input Data

Stochastic collocation methods for approximating the solution of partial differential equations with random input data (e.g., coefficients and forcing terms) suffer from the curse of dimensionality whereby increases in the stochastic dimension cause an explosion of the computational effort. We propose and analyze a multilevel version of the stochastic collocation method that, as is the case for multilevel Monte Carlo (MLMC) methods, uses hierarchies of spatial approximations to reduce the overall computational complexity. In addition, our proposed approach utilizes, for approximation in stochastic space, a sequence of multidimensional interpolants of increasing fidelity which can then be used for approximating statistics of the solution as well as for building high-order surrogates featuring faster convergence rates. A rigorous convergence and computational cost analysis of the new multilevel stochastic collocation method is provided in the case of elliptic equations, demonstrating its advantages compared to standard single-level stochastic collocation approximations as well as MLMC methods. Numerical results are provided that illustrate the theory and the effectiveness of the new multilevel method.