Both forward (spatial to spectral) and inverse (spectral to spatial) Fourier transform routines are provided, as well as examples of how they may be used, e.g. pattern matching on the sphere via correlation. A preprint is available which offers a detailed theoretical development and description of the algorithms implemented in SOFT, as well as numerical and timing results, and some discussion of applications.

Subsets of SpharmonicKit and S2kit necessary for some of the routines and examples are also included. (The complete SpharmonicKit and S2kit distributions are both available here.) Also, variations of some SOFT routines are provided which use the more efficient FFTW collection (version 3, to be precise), and not our home-grown FFT code.

SOFT is free software and is distributed under the terms of the GNU General Public License.

Caveat emptor - this is research code only and has not been hardened. The code was developed and tested in the GNU/Linux environment. Some of the code has also been successfully compiled and executed on a Macintosh (PowerPC) running OS 10.3.9 and 10.4.10, an SGI running Irix 6.5, an HP/Compaq Alpha running Tru64 V5.1, and even (under VMware) OpenStep 4.2 for Intel! I do not have access to a Windows machine. However, I do not see there being any reason why the code won't compile and run under Windows. A minor modification or two might be required, but I do not believe anything drastic should be necessary.

What's New

Papers

Source Code

What's New

(updated 23 Apr 2008)

Bug fix	(23 Apr 2008) A user has recently identified a bug which exists in a source file found in the SpharmonicKit 2.7, S2kit 1.0 and SOFT 2.0 distributions. (I.e. Slight variations of this file are included in all three distributions.) Fortunately, the fix is an easy one. The bug's description and cure may be found in this document.
Version 2.0 of SOFT released	(16 Sep 2007) At long last (you do not want to know how long), Version 2.0 is released. In addition to a couple of bug fixes, the big news is that the FFTW-based routines in SOFT can now handle problem sizes of arbitrary, i.e. non powers-of-2, bandwidth. Further information can be found in this pdf file, which is also included within the distribution.
Bug fix for SOFT 1.0	(20 Feb 2006) Bug fix - Thanks to feedback from a user, errors were found in two of the example routines contained within the distribution. Basically, the for-loops responsible for reading in the sample data, prior to transforming, in the correlation examples were too long. This pdf file contains a description of the problem, and its solution. We apologize for any problems this error may have caused.
Version 1.0 of SOFT released	(15 Nov 2003) Version 1.0 released. Will wonders never cease.

Papers Available

• FFTs on the Rotation Group

  Earlier work by Driscoll and Healy has produced an efficient $O(B^2\log^2 B)$ algorithm for computing the Fourier transform of band-limited functions on the 2-sphere. In this paper, we discuss an implementation of an $O(B^4)$ algorithm for the numerical computation of Fourier transforms of functions defined on the rotation group, $SO(3)$. This compares with the direct $O(B^6)$ approach. The algorithm we implemented is based on the ``Separation of Variables'' approach, e.g. as presented by Maslen and Rockmore (see paper below). In conjunction with the techniques developed by Driscoll and Healy, the $SO(3)$ algorithm we implemented may be made truly fast, $O(B^3\log^2 B)$. Basic results will be presented establishing the algorithm's numerical stability, and examples of applications will be presented.
  
  
  • P. J. Kostelec and D. N. Rockmore, "FFTs on the Rotation Group," Santa Fe Institute Working Papers Series Paper #03-11-060, 2003, pdf.
    (January 2008) An updated and revised version of this preprint will appear in The Journal of Fourier Analysis and Applications.

• Generalized FFTs -- A survey of some recent results

  In this paper we survey some recent work directed towards generalizing the fast Fourier transform (FFT). We work primarily from the point of view of group representation theory. In this setting the classical FFT can be viewed as a family of efficient algorithms for computing the Fourier transform of either a function defined on a finite abelian group, or a bandlimited function on a compact abelian group. We discuss generalizations of the FFT to arbitrary finite groups and compact Lie groups.
  
  
  • D. Maslen and D. Rockmore, "Generalized FFTs -- A survey of some recent results" Proc. 1995 DIMACS Workshop in Groups and Computation, L. Finkelstein and W. Kantor (eds.), Dimacs Series in Disc. Math. and Comp. Sci, Volume 28, pp. 183--238. .ps or .pdf.

The Source Code

SOFT 2.0 (latest release)	Here is a document explaining the contents of SOFT. (It is also included within the distribution.) Version 2.0 is available in the following formats: .tgz (around 670 kilobytes) .zip (around 775 kilobytes)
SOFT 1.0 (previous release) (not supported)	For users requiring the debut release ... Version 1.0 is available in the following formats: .tar.gz (around 480 kilobytes) .zip (around 570 kilobytes)

This work has been funded in part by NSF AWARD DMS-0219717.

There have been 10029 visitors since 18 Jun 2004. They mean you no harm.

Return to Fast Fourier Analysis on Groups.