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

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:
http://dx.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