Remote Access Mathematics of Computation
Green Open Access

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. B. K. Alpert and V. Rokhlin, ``A Fast Algorithm for the Evaluation of Legendre Expansions'', SIAM J. Sci. Stat. Comput., Vol. 12, No. 1, pp. 158-179, 1991. MR 91i:65042
  • 2. G. Beylkin, R. R. Coifman, and V. Rokhlin, ``Fast Wavelet Transforms and Numerical Algorithms I'', Comm. Pure Appl. Math. No. 44, pp. 141-183, 1991. MR 92c:65061
  • 3. J. P. Boyd, ``Multipole expansions and pseudospectral cardinal functions: A new generation of the fast Fourier transform'', J. Comput. Phys., Vol. 103, pp. 184-186, 1992. MR 93h:65175
  • 4. A. Dutt, M. Gu, and V. Rokhlin, ``Fast algorithms for polynomial interpolation, integration, and differentiation'', SIAM J. Numer. Anal., Vol. 33, No. 5, pp. 1689-1711, 1996. MR 97h:65015
  • 5. L. Greengard and V. Rokhlin, ``A fast algorithm for particle simulations'', J. Comput. Phys., Vol. 73, pp. 325-348, 1987. MR 88k:82007
  • 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. -, ``A Fast Transform for Spherical Harmonics'', J. Fourier Anal. Appl., Vol. 2, pp. 159-184, 1999. MR 2000b:65247
  • 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. D. Potts, G. Steidl, and M. Tasche, ``Fast and stable algorithms for discrete spherical Fourier transforms'', Linear Algebra Appl. pp. 433 - 450, 1998. MR 99h:65229
  • 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

American Mathematical Society