Fast expansion into harmonics on the ball

Abstract

We devise fast and provably accurate algorithms to transform between an $N\times N\times N$ Cartesian voxel representation of a three-dimensional function and its expansion into the {ball harmonics}, that is, the eigenbasis of the Dirichlet Laplacian on the unit ball in ${\mathbb{R}}^3$. Given $\epsilon >0$, our algorithms achieve relative ${\ell }^1$ - ${\ell }^{\infty }$ accuracy $\epsilon$ in time $O(N^3(\log N{)}^2+N^3|\log \epsilon {|}^2)$, while the naïve direct application of the expansion operators has time complexity $O(N^6)$. We illustrate our methods on numerical examples.

31 pages, 4 figures, 2 tables