A fast discrete spectral method for stochastic partial differential equations

The goal of this paper is to construct an efficient numerical algorithm for computing the coefficient matrix and the right hand side of the linear system resulting from the spectral Galerkin approximation of a stochastic elliptic partial differential equation. We establish that the proposed algorithm achieves an exponential convergence with requiring only O\((n\log _{2}^{d+1}n)\) number of arithmetic operations, where n is the highest degree of the one dimensional orthogonal polynomial used in the algorithm, d+1 is the number of terms in the finite Karhunen–Loéve (K-L) expansion. Numerical experiments confirm the theoretical estimates of the proposed algorithm and demonstrate its computational efficiency.