A fast spherical harmonics transform algorithm

Authors:
Reiji Suda and Masayasu Takami

Journal:
Math. Comp. **71** (2002), 703-715

MSC (2000):
Primary 65T99, 42C10

DOI:
https://doi.org/10.1090/S0025-5718-01-01386-2

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 for cut-off frequency . 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 . Experimental results show that our algorithm is stable and is faster than the direct computation for .

**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).

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

Email:
reiji@na.cse.nagoya-u.ac.jp

**Masayasu Takami**

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

Email:
m-takami@kubota.co.jp

DOI:
https://doi.org/10.1090/S0025-5718-01-01386-2

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