A fast spherical harmonics transform algorithm

Suda, Reiji; Takami, Masayasu

doi:10.1090/S0025-5718-01-01386-2

A fast spherical harmonics transform algorithm
HTML articles powered by AMS MathViewer

by Reiji Suda and Masayasu Takami PDF

Math. Comp. 71 (2002), 703-715 Request permission

Abstract:

The spectral method with discrete spherical harmonics transform plays an important role in many applications. In spite of its advantages, the spherical harmonics transform has a drawback of high computational complexity, which is determined by that of the associated Legendre transform, and the direct computation requires time of $O(N^3)$ for cut-off frequency $N$. In this paper, we propose a fast approximate algorithm for the associated Legendre transform. Our algorithm evaluates the transform by means of polynomial interpolation accelerated by the Fast Multipole Method (FMM). The divide-and-conquer approach with split Legendre functions gives computational complexity $O(N^2 \log N)$. Experimental results show that our algorithm is stable and is faster than the direct computation for $N \ge 511$.

References

Bradley K. Alpert and Vladimir Rokhlin, A fast algorithm for the evaluation of Legendre expansions, SIAM J. Sci. Statist. Comput. 12 (1991), no. 1, 158–179. MR 1078802, DOI 10.1137/0912009
G. Beylkin, R. Coifman, and V. Rokhlin, Fast wavelet transforms and numerical algorithms. I, Comm. Pure Appl. Math. 44 (1991), no. 2, 141–183. MR 1085827, DOI 10.1002/cpa.3160440202
John P. Boyd, Multipole expansions and pseudospectral cardinal functions: a new generalization of the fast Fourier transform, J. Comput. Phys. 103 (1992), no. 1, 184–186. MR 1188093, DOI 10.1016/0021-9991(92)90333-T
A. Dutt, M. Gu, and V. Rokhlin, Fast algorithms for polynomial interpolation, integration, and differentiation, SIAM J. Numer. Anal. 33 (1996), no. 5, 1689–1711. MR 1411845, DOI 10.1137/0733082
L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys. 73 (1987), no. 2, 325–348. MR 918448, DOI 10.1016/0021-9991(87)90140-9
D. M. Healy Jr., D. Rockmore, P. J. Kostelec, and S. S. B. Moore, “FFTs for 2-Sphere — Improvements and Variations”, Tech. Rep. PCS-TR96-292, Dartmouth Univ., 1996.
R. Jakob-Chien and B. K. Alpert, “A Fast Spherical Filter with Uniform Resolution”, J. Comput. Phys., Vol. 136, pp. 580-584, 1997.
M. J. Mohlenkamp, “A Fast Transform for Spherical Harmonics”, PhD dissertation, Yale University, 1997.
Martin J. Mohlenkamp, A fast transform for spherical harmonics, J. Fourier Anal. Appl. 5 (1999), no. 2-3, 159–184. MR 1683208, DOI 10.1007/BF01261607
A. Mori, R. Suda and M. Sugihara, “An improvement on Orszag’s Fast Algorithm for Legendre Polynomial Transform”, Trans. Inform. Process. Soc. Japan, Vol. 40, No. 9, pp. 3612–3615 (1999).
S. A. Orszag, “Fast Eigenfunction Transforms”, Academic Press: Science and Computers, Adv. Math. Supplementary Studies, Vol. 10, pp. 23-30, 1986.
Daniel Potts, Gabriele Steidl, and Manfred Tasche, Fast and stable algorithms for discrete spherical Fourier transforms, Proceedings of the Sixth Conference of the International Linear Algebra Society (Chemnitz, 1996), 1998, pp. 433–450. MR 1628403, DOI 10.1016/S0024-3795(97)10013-1
J. H. Reif and S. R. Tate, “N-body Simulation I: Fast Algorithms for Potential Field Evaluation and Trummer’s Problem”, Tech. Rep. N-96-002, Univ. of North Texas, Dept. of Computer Science (1996).