This paper considers the problem of efficient computation of the spher
ical harmonic expansion, or Fourier transform, of functions defined on
the two dimensional sphere, S2. The resulting algorithms are applied
to the efficient computation of convolutions of functions on the spher
e. We begin by proving convolution theorems generalizing well known an
d useful results from the abelian case. These convolution theorems are
then used to develop a sampling theorem on the sphere. which reduces
the calculation of Fourier transforms and convolutions of band-limited
functions to discrete computations. We show how to perform these effi
ciently, starting with an O(n(log n)2 )time algorithm for computing th
e Legendre transform of a function defined on the interval [-1,1] samp
led at n points there. Theoretical and experimental results on the eff
ects of finite precision arithmetic are presented. The Legendre transf
orm algorithm is then generalized to obtain an algorithm for the Fouri
er transform, requiring O(n(log n)2) time, and an algorithm for its in
verse in O(n 1.5) time, where n is the number of points on the sphere
at which the function is sampled. This improves the naive O(n2) bound,
which is the best previously known. These transforms give an O(n1.5)
algorithm for convolving two functions on the sphere. (C) 1994 Academi
c Press, Inc.