Fast expansion into harmonics on the ball

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 ${\mathrm{\ell }}^1$ - ${\mathrm{\ell }}^{\mathrm{\infty }}$ accuracy $\epsilon$ in time $O(N^3(\log N{)}^2+N^3\mathrm{\mid }\log \epsilon {\mathrm{\mid }}^2)$, while the naïve direct application of the expansion operators has time complexity $O(N^6)$. We illustrate our methods on numerical examples.