PIMS-SFU CSC Seminar: Richard Mikael Slevinsky

Spherical harmonics are the natural basis for square integrable functions on the sphere in the sense of Lebesgue. However, their analytic structure makes them formidable to work with numerically. In this talk, we will present rapid transformations between spherical harmonic expansions and their analogues in a bivariate Fourier series. The change of basis is described in two steps: firstly, expansions in normalized associated Legendre functions of all orders are converted to those of order zero and one; then, these intermediate expressions are re-expanded in trigonometric form. Total pre-computation requires at best $\mathcal{O}(n^3\log n)$ flops; and, asymptotically optimal execution time of $\mathcal{O}(n^2\log^2 n)$ is rigorously proved via connection to Fourier integral operators.

Next, we describe a skeletonization of the spherical harmonic connection problem that reduces the storage and pre-computation to superoptimal complexities at the cost of increasing the execution time by the modest multiplicative factor of $\mathcal{O}(\log n)$. The proposed skeletonization maximizes the interconnectivity by overlaying a dyadic partitioning on the connection problem. An application of current interest is the time evolution of PDEs with nonlocal operators. The utility of spherical harmonics comes to the fore when they are found to be the eigenfunctions of a class of nonlocal operators on the sphere.