SPARSE TENSOR DISCRETIZATION OF ELLIPTIC SPDES

We propose and analyze sparse deterministic-stochastic tensor Galerkin finite element methods (sparse sGFEMs) for the numerical solution of elliptic partial differential equations (PDEs) with random coefficients in a physical domain D subset of R-d. In tensor product sGFEMs, the variational solution to the boundary value problem is approximated in tensor product finite element spaces V-Gamma circle times V-D, where V-Gamma and V-D denote suitable finite dimensional subspaces of the stochastic and deterministic function spaces, respectively. These approaches lead to sGFEM algorithms of complexity O(N Gamma ND), where N-Gamma = dim V-Gamma and N-D = dim V-D. In this work, we use hierarchic sequences V-1(Gamma) subset of V-2(Gamma) subset of ... and V-1(D) subset of ... of finite dimensional spaces to approximate the law of the random solution. The hierarchies of approximation spaces allow us to define sparse tensor product spaces V-l(Gamma) (circle times) over cap V-l(D), l = 1, 2, ... , yielding algorithms of O(N-Gamma log N-D + N-D log N-Gamma) work and memory. We estimate the convergence rate of sGFEM for algebraic decay of the input random field Karhunen-Loeve coefficients. We give an algorithm for an input adapted a-priori selection of deterministic and stochastic discretization spaces. The convergence rate in terms of the total number of degrees of freedom of the proposed method is superior to Monte Carlo approximations. Numerical examples illustrate the theoretical results and demonstrate superiority of the sparse tensor product discretization proposed here versus the full tensor product approach.