Yanzhao Cao, Ying Jiang, Yuesheng Xu
Abstract: A fast algorithm is developed to compute orthogonal polynomial expansions on sparse grids for a function of $d$ variables in a weighted $L^2$
space. The proposed algorithm combines the fast cosine transform, a fast transform from the Chebyshev orthogonal polynomial basis to the orthogonal polynomial basis for the weighted $L^2$ space and a fast algorithm of computing hierarchically structured basis functions. The overall computational complexity of the algorithm $O(n\log^{d+1}n)$ where $n$ is the highest polynomial degree in one dimension. Exponential convergence under an analyticity assumption is proved. Numerical experiments con rm the theoretical results and demonstrate the efficiency of the proposed algorithm.
Preprint