Orthogonal polynomial expansions on sparse grids

We study the orthogonal polynomial expansion on sparse grids for a function of dd variables in a weighted L2L2 space. Two fast algorithms are developed for computing the orthogonal polynomial expansion and evaluating a linear combination of orthogonal polynomials on sparse grids by combining the fast cosine transform, the fast transforms between the Chebyshev orthogonal polynomial basis and the orthogonal polynomial basis for the weighted L2L2 space, and a fast algorithm of computing hierarchically structured basis functions. The total number of arithmetic operations used in both algorithms is O(nlogd+1n)O(nlogd+1n) where nn is the highest polynomial degree in one dimension. The exponential convergence of the approximation for the analytic function is investigated. Specifically, we show the sub-exponential convergence for analytic functions and moreover we prove the approximation order is optimal for the Chebyshev orthogonal polynomial expansion. We furthermore establish the fully exponential convergence for functions with a somewhat stronger analytic assumption. Numerical experiments confirm the theoretical results and demonstrate the efficiency and stability of the proposed algorithms.