Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A fast spherical harmonics transform algorithm

Authors: Reiji Suda and Masayasu Takami
Journal: Math. Comp. 71 (2002), 703-715
MSC (2000): Primary 65T99, 42C10
Published electronically: November 28, 2001
MathSciNet review: 1885622
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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, 10.1137/0912009
  • 2. 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, 10.1002/cpa.3160440202
  • 3. 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, 10.1016/0021-9991(92)90333-T
  • 4. 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, 10.1137/0733082
  • 5. L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys. 73 (1987), no. 2, 325–348. MR 918448, 10.1016/0021-9991(87)90140-9
  • 6. 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.
  • 7. R. Jakob-Chien and B. K. Alpert, ``A Fast Spherical Filter with Uniform Resolution'', J. Comput. Phys., Vol. 136, pp. 580-584, 1997.
  • 8. M. J. Mohlenkamp, ``A Fast Transform for Spherical Harmonics'', PhD dissertation, Yale University, 1997.
  • 9. Martin J. Mohlenkamp, A fast transform for spherical harmonics, J. Fourier Anal. Appl. 5 (1999), no. 2-3, 159–184. MR 1683208, 10.1007/BF01261607
  • 10. 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). CMP 2000:04
  • 11. S. A. Orszag, ``Fast Eigenfunction Transforms'', Academic Press: Science and Computers, Adv. Math. Supplementary Studies, Vol. 10, pp. 23-30, 1986.
  • 12. 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, 10.1016/S0024-3795(97)10013-1
  • 13. 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).

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65T99, 42C10

Retrieve articles in all journals with MSC (2000): 65T99, 42C10

Additional Information

Reiji Suda
Affiliation: Department of Computational Science and Engineering, Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 464-8603, Japan

Masayasu Takami
Affiliation: Department of Computational Science and Engineering, Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 464-8603, Japan

Keywords: Spherical harmonics transform, associated Legendre transform, fast transform algorithm, computational complexity
Received by editor(s): January 24, 2000
Received by editor(s) in revised form: July 10, 2000
Published electronically: November 28, 2001
Additional Notes: This research is partly supported by the Japan Society for Promotion of Science (Computational Science and Engineering for Global Scale Flow Systems Project), Grant-in-Aid #11450038 of the Ministry of Education, and the Toyota Physical and Chemical Research Institute.
Article copyright: © Copyright 2001 American Mathematical Society