BIB-VERSION:: CS-TR-v2.0 ID:: ncstrl.dartmouthcs//TR2002-419 ENTRY:: August 19, 2002 ORGANIZATION:: Dartmouth College, Computer Science TITLE:: FFTs for the 2-Sphere - Improvements and Variations TYPE:: Technical Report (paper) REVISION:: 1 AUTHOR:: Healy, Dennis M. AUTHOR:: Rockmore, Daniel N. AUTHOR:: Kostelec, Peter J. AUTHOR:: Moore, Sean S. B. DATE:: March 2002 RETRIEVAL:: For a paper copy, email RETRIEVAL:: For a paper copy, write to Technical Report Librarian Department of Computer Science Dartmouth College 6211 Sudikoff Laboratory Hanover, NH 03755-3510 USA RETRIEVAL:: Compressed Postscript at http://www.cs.dartmouth.edu/reports/TR2002-419.ps.Z RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR2002-419.pdf ABSTRACT:: Earlier work by Driscoll and Healy has produced an efficient algorithm for computing the Fourier transform of band-limited functions on the 2-sphere. In this paper we present a reformulation and variation of the original algorithm which results in a greatly improved inverse transform, and consequent improved convolution algorithm for such functions. All require at most $O(N\log^2 N)$ operations where $N$ is the number of sample points. We also address implementation considerations and give heuristics for allowing reliable and computationally efficient floating point implementations of slightly modified algorithms. These claims are supported by extensive numerical experiments from our implementation in C on DEC, HP, SGI and Linux Pentium platforms. These results indicate that variations of the algorithm are both reliable and efficient for a large range of useful problem sizes. Performance appears to be architecture-dependent. The paper concludes with a brief discussion of a few potential applications. NOTE:: Preliminary versions of some of these results have appeared in the Dartmouth College Department of Computer Science Technical Report PCS-TR94-222 and ``An FFT for the 2-sphere and Applications'', Proc. of ICASSP-96, Volume 3, pp. 1323--1326. END:: ncstrl.dartmouthcs//TR2002-419