Fast and backward stable transforms between spherical harmonic expansions and bivariate Fourier series
This work provides a computationally efficient and stable method for converting between spherical harmonics and Fourier series, benefiting applications in geophysics, astrophysics, and numerical analysis that require such transforms.
The authors derive a fast and backward stable transform between spherical harmonic expansions and bivariate Fourier series, achieving asymptotically optimal execution time of O(n^2 log^2 n) with pre-computation of O(n^3 log n) flops.
A rapid transformation is derived 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. The first step proceeds with a butterfly factorization of the well-conditioned matrices of connection coefficients. The second step proceeds with fast orthogonal polynomial transforms via hierarchically off-diagonal low-rank matrix decompositions. 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.