COMPUTING FOURIER-TRANSFORMS AND CONVOLUTIONS ON THE 2-SPHERE

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.