A fast transform for spherical harmonics
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.
scientific article; zbMATH DE number 1310351