Sparse perturbation algorithms for elliptic problems with stochastic data

We consider the moment problem for an elliptic pde with stochastic data posed in a bounded physical domain. We develop perturbation algorithms of nearly optimal complexity for the moment computation of the stochastic solution, assuming spatial regularity of the random fluctuation in the data. Techniques used include sparse grids, wavelet preconditioning and best N-term approximation for the efficient representation of higher order moments.