2017/05/15 by Slevinsky, Richard Mikael · 1 citation
#33C55 #65F99 #65Y99 #FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.1705.05448
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 O(n3log n) flops; and, asymptotically optimal execution time of O(n2log2 n) is rigorously proved via connection to Fourier integral operators.