Accelerating Stochastic Collocation Methods for Partial Differential Equations with Random Input Data

This work proposes and analyzes a generalized technique for decreasing the computational complexity of stochastic collocation (SC) methods to solve partial differential equations (PDEs) with random input data. Specifically, we predict the solution of the parametrized PDE at each collocation point using a previously assembled lower fidelity interpolant and use this prediction to provide deterministic (linear/nonlinear) iterative solvers with initial approximations which continue to improve as the algorithm progresses through the levels of the interpolant. With nested collocation points, these coarse predictions can be assembled as a substep in the construction of the high-fidelity interpolant. As a concrete example, we develop our approach in the context of SC approaches employing sparse tensor products of globally defined Lagrange polynomials on nested one-dimensional Clenshaw Curtis abscissas, providing a rigorous computational complexity analysis of the resulting fully discrete sparse grid SC approximation, with and without acceleration, and demonstrating the effectiveness of our proposed algorithm. Numerical examples include linear and nonlinear parametrized PDEs and illustrate the theoretical results and the improved efficiency of this technique compared with several others.