Fast algorithms for spherical harmonic expansions. II. (Q2427341)

The fast Fourier transform (FFT) is an efficient algorithm for computing, for any \(n\in\mathbb{N}\) and \(\{\beta_0,\beta_1,\dots, \beta_{n-1}\}\subset\mathbb{C}\), the numbers \[ \alpha_j:= \sum^{m-1}_{k=0} \beta_k e_k(x_j),\qquad j= 0,1,\dots, n-1, \] where \[ e_k(x):= \exp\Biggl({\pi_i(2k- n)x\over 2}\Biggr)\text{ and }x_k:= {2k- n\over n},\quad k= 0,1,\dots, n-1. \] As is well-known, the FFT requires at most \(Cn\ln n\) floating point operations to compute \(\alpha_0,\) \(\alpha_1,\dots, \alpha_{n-1}\) form \(\beta_0,\beta_1,\dots, \beta_{n-1}\), where \(C\) is an absolute constant. The aim of the present paper is to elaborate an analogue of the FFT for functions defined on the two-dimensional surface of the unit sphere in \(\mathbb{R}^3\), in the following sense. The spherical harmonic expansion of a bandlimited function \(f\) on the surface of the sphere is of the form \[ f(\theta,\varphi):= \sum^{2\ell-1}_{k=0} \sum^k_{m=-k} \beta^m_k\overline P^{|m|}_k(\cos\theta) e^{im\varphi}, \] where \((\theta,\pi)\) are the spherical coordinates, \(\theta\in (0,\pi)\) and \(\varphi\in (0,2\pi)\), and \(\overline P^{|m|}_k\) is the normalized associated Legendre function of degree \(k\) and order \(|m|\) defined on \((-1, 1)\). Efficient algorithms are provided for calculating the coefficients in the spherical harmonic expansions of functions that are specified by their values at some appropriately chosen points. The algorithms are numerically stable and have costs proportional to \(\ell^2\ln\ell\). Several numerical examples illustrate the performance of the algorithms. [For part I see \textit{V. Rokhlin} and \textit{M. Tygert}, SIAM J. Sci. Comput. 27, No.~6, 1903--1928 (2006; Zbl 1104.65134).]