Abstract
Spherical harmonics arise on the sphere S2 in the same way that the (Fourier) exponential functions {eikθ}k∈ℤ arise on the circle. Spherical harmonic series have many of the same wonderful properties as Fourier series, but have lacked one important thing: a numerically stable fast transform analogous to the Fast Fourier Transform (FFT). Without a fast transform, evaluating (or expanding in) spherical harmonic series on the computer is slow—for large computations probibitively slow. This paper provides a fast transform.
For a grid ofO(N2) points on the sphere, a direct calculation has computational complexityO(N4), but a simple separation of variables and FFT reduce it toO(N3) time. Here we present algorithms with timesO(N5/2 log N) andO(N2(log N)2).
The problem quickly reduces to the fast application of matrices of associated Legendre functions of certain orders. The essential insight is that although these matrices are dense and oscillatory, locally they can be represented efficiently in trigonometric series.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alpert, B. and Rokhlin, V. (1991). A fast algorithm for the evaluation of Legendre expansions,SIAM J. Sci. Stat. Comp., 12(sn1), 158–179.
Abramowitz, M. and Stegun, I.A. (1964).Handbook of Mathematical Functions, Vol. 55of Applied Math Series, National Bureau of Standards.
Bradie, B., Coifman, R., and Grossmann, A. (1993). Fast numerical computations of oscillatory integrals related to acoustic scattering,Appl. Comp. Harmon. Anal.,1, 94–99.
Beylkin, G., Coifman, R., and Rokhlin, V. (1991). Fast wavelet transforms and numerical algorithms,Comm. Pure Appl. Math.,44, 141–183.
Bennet, N.N. (1997). Signal Analysis of Chirps: Detection, Oscillatory Kernels, and Anisotropic Wavelets, Ph.D. Thesis, Yale University, New Haven, CT.
Bender, C.M. and Orzag, S.A. (1978).Advanced Mathematical Methods for Scientists and Engineers, International series in pure and applied mathematics, McGraw-Hill, New York.
Brown, T.M. (1985). Solar rotation as a function of depth and latitude,Nature,317(sn17), 591–594.
Coifman, R.R. and Meyer, Y. (1991). Remarques sur l'analyse de Fourier à fenêtre,C.R. Académie des Sciences,312(1), 259–261.
Duvall, Jr., T.L., Elowitz, M., and Hill, F. (1989). A test of a modified algorithm for computing spherical harmonic coefficients using an fft,J. Comp. Phys.,80, 506–511.
Driscoll, J.R. and Healy, Jr., D.M. (1994). Computing Fourier transforms and convolutions on the 2-sphere,Adv. in Appl. Math.,15, 202–250.
Dilts, G.A. (1985). Computation of spherical harmonic expansion coefficients via fft's,J. Comp. Phys.,57, 439–453.
Erdélyi, A., Magnus, W., Oberhettinger, F., and Tricomi, F.G. (1954).Tables of Integral Transforms, McGraw-Hill, New York.
Flannery, B., Press, W., Teukolsky, S., and Vettering, W. (1992).Numerical Recipies in C, 2nd ed., Cambridge University Press, Cambridge, UK.
Hobson, E.W. (1931).The Theory of Spherical and Ellipsoidal Harmonics, Chelsea, New York.
Landau, L.D. and Lifschitz, E.M. (1977).Quantum Mechanics (Non-Relativistic Theory, 3rd ed., Pergamon Press, New York.
Matviyenko, G. (1996). Optimized local trigonometric bases,Appl. Comp. Harmon. Anal.,3(sn4), 301–323.
Mohlenkamp, M.J. (1997).A Fast Transform for Spherical Harmonics, Ph.D. Thesis, Yale University, New Haven, CT.
Orszag, S.A. (1986). Fast eigenfunction transforms,Advances in Mathematics Supplementary Studies,10.
Stein, E. andWeiss, G. (1971).Fourier Analysis on Euclidean Spaces, Princeton University Press, Princeton, NJ.
Szegö, G. (1975).Orthogonal Polynomials, 4th ed., AMS, Providence, RI.
Thiele, C.M. and Villemos, L.F. (1996). A fast algorithm for adapted time-frequency tilings,Appl. Comp. Harmon. Anal.,3(sn2), 91–99.
Wickerhauser, M.V. (1994).Adapted Wavelet Analysis from Theory to Software, Peters, A.K., Wellesley, MA.
Author information
Authors and Affiliations
Additional information
Communicated by M. Victor Wickerhauser
Rights and permissions
About this article
Cite this article
Mohlenkamp, M.J. A fast transform for spherical harmonics. The Journal of Fourier Analysis and Applications 5, 159–184 (1999). https://doi.org/10.1007/BF01261607
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01261607