Fast and backward stable transforms between spherical harmonic expansions and bivariate Fourier series

摘要

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(n(3) log n) flops; and, asymptotically optimal execution time of O(n(2) log(2) n) is rigorously proved via connection to Fourier integral operators. (C) 2017 Elsevier Inc. All rights reserved.