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 $R^3$ . Given $\epsilon >0$ , our algorithms achieve relative ${\ell }^1-{\ell }^{\infty }$ accuracy $\epsilon$ in time $𝒪\left(N^3(logN{)}^2+N^3|log\epsilon {|}^2\right)$ , while the naive direct application of the expansion operators has time complexity $𝒪\left(N^6\right)$ . We illustrate our methods on numerical examples.