Fast Algorithms for Spherical Harmonic Expansions

Abstract

An algorithm is introduced for the rapid evaluation at appropriately chosen nodes on the two-dimensional sphere $S^2$ in ${\mathbb R}^3$ of functions specified by their spherical harmonic expansions (known as the inverse spherical harmonic transform), and for the evaluation of the coefficients in spherical harmonic expansions of functions specified by their values at appropriately chosen points on $S^2$ (known as the forward spherical harmonic transform). The procedure is numerically stable and requires an amount of CPU time proportional to $N^2 (\log N) \log(1/\epsilon)$, where $N^2$ is the number of nodes in the discretization of $S^2$, and $\epsilon$ is the precision of computations. The performance of the algorithm is illustrated via several numerical examples.