A fast transform for spherical harmonics (Q1293826)

The author develops the first numerically stable fast algorithm for the computation of the discrete spherical transform (and its inverse) \[ f(\varphi_j,\theta_k)= \sum^{N- 1}_{n=0} \sum^n_{m=- n}\alpha^m_n P^m_n(\cos\varphi_j) e^{im\theta_k}/\sqrt{2\pi} \] (\(j= 0,\dots, N-1\); \(k=0,\dots, 2N-1\)), where \(\varphi_j:= \arccos g^N_j\) (\(g^N_j\) Gaussian nodes) and \(\theta_k:= {2\pi k\over 2N}\). Note that the algorithm of \textit{J. R. Driscoll} and \textit{D. M. Healy, jun.} [Adv. Appl. Math. 15, No. 2, 202-250 (1994; Zbl 0801.65141)] for the fast spherical transform is not stable and that certain stabilization techniques of \textit{D. Potts}, \textit{G. Steidl} and \textit{M. Tasche} [Linear Algebra Appl. 275-276, 433-450 (1998; reviewed above)] cannot ensure the arithmetical complexity of \(O(N^2\log^2N)\). The authors presents algorithms with computational complexity \(O(N^2\log^2 N)\) and \(O(N^{{5\over 2}}\log N)\) based on local cosine bases. The essential insight is that although the transform matrices are dense and oscillatory, locally they can be represented efficiently in trigonometric series.