The SOFT Package:
FFTs on the Rotation Group

SOFT is a collection of C routines which compute the discrete Fourier transform of a function defined on SO(3), i.e. the famous Rotation Group. (So SOFT equals "SO(3) Fourier Transforms.") The algorithms implemented in this collection are based on the "Separation of Variables" technique (e.g. see the paper by D. Maslen and D. Rockmore below). The complexity is O(B^4), where B is the bandwidth. This compares with the direct O(B^6) algorithm.

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

The following preprint offers a detailed theoretical development and description of the algorithms implemented in SOFT, as well as numerical and timing results. Related to the above, the following is a survey of recent work directed towards generalizing the FFT. Included is discussion of the Separation of Variables technique.

The Source Code

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

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 visitors since 18 Jun 2004. They mean you no harm.

Return to Fast Fourier Analysis on Groups.


Last modified: 23 Apr 2008