We consider the computational complexity of approximating elliptic PDEs with random coefficients by sparse product polynomial expansions. Except for special cases (for instance, when the spatial discretisation limits the achievable overall convergence rate), previous approaches for a posteriori selection of polynomial terms and corresponding spatial discretizations do not guarantee optimal complexity in the sense of computational costs scaling linearly in the number of degrees of freedom. We show that one can achieve optimality of an adaptive Galerkin scheme for discretizations by spline wavelets in the spatial variable when a multiscale representation of the affinely parameterized random coefficients is used. Moreover, some first results of the generalization of this approach to standard finite element discretizations will be presented.
M. Bachmayr and I. Voulis, An adaptive stochastic Galerkin method based on multilevel expansions of random fields: Convergence and optimality, arXiv:2109:09136