The Legendre transforms in the Kit require that a function of bandwidth B be sampled on the 2B-many Chebyshev points and not the B-many Gaussian points. Therefore, the number of samples needed is twice the function's bandwidth. This implies that for the spherical transforms in the Kit, a function of bandwidth B is sampled on the equiangular 2Bx2B grid on the sphere.

Some of the algorithms implemented in this package are based on the work of Driscoll and Healy. A preprint that offers a detailed development and description of the algorithms implemented in SpharmonicKit is here.

Caveat emptor - this is research code only and has not been hardened. All the code works quite well on DEC Alpha workstations using OSF1 Versions 3.2 and 4.0. Some code has also been tested and successfully run on Pentium-based GNU/Linux workstations, SGI workstations using IRIX 5.3 and IRIX 6.4, Sun workstations using SunOS 4.1.2 1, an HP Exemplar X-Class running SPP-UX 5.2.1, and even a NeXTstation Color Turbo running NeXTStep 3.3!

We would also like to mention that there exists other software for performing spherical transforms. Details on other possibilities may be found here.

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.
SOFT 2.0 released	(16 Sept 2007) Yes, another shameless plug. SOFT 2.0, a collection of code for taking Fourier transforms of functions defined on SO(3), has been released and is available here. The major difference between this release and the v.1.0 is that the user, with the help of FFTW, is no longer restricted to doing transforms at powers-of-2 bandwidths.
Version 1.0 of S2kit released	(20 Feb 2004) S2kit is a lite version of SpharmonicKit. (Hence the shorter name.) It is a collection of routines, written in C, which implement discrete Legendre and spherical harmonic transforms. In addition to code being cleaned up, S2kit is lite mainly for two reasons. Firstly, it uses only two types of discrete Legendre transform (DLT) algorithms: the naive and semi-naive algorithms. These algorithms are described in the preprint below, as well as this document which is included with the S2kit distribution. Secondly, S2kit absolutely requires version 3 of FFTW. The routines in FFTW are more efficient than our home-grown code, and, perhaps more importantly, the user is no longer restricted to doing transforms at powers-of-2 bandwidths (which is the case with SpharmonicKit).
Version 2.7 released	(19 Feb 2004) Bug fix - Thanks to feedback from a user, another (and hopefully last) scaling error was identified and fixed. This time, it was in a routine having to do with convolutions. Details of the fix may be found in the CHANGES file which accompanies the distribution.
Version 1.0 of SOFT released	(15 Nov 2003) Code for taking Fourier transforms of functions defined on SO(3), aka the Rotation Group, is available here. (Yes, this is a shameless plug.) Included within this distribution are examples of how the code may be used, e.g. correlating, and rotating, functions defined on the sphere.
Version 2.6 released	(July 2003) Bug fix - Thanks to feedback from a user, an ancient scaling discrepancy has been identified and corrected. Internally, the normalizations are all consistent with one another and hence, as far as the code is concerned, correct. Details of the fix may be found in the CHANGES file which accompanies the distribution.
Version 2.5 released	Version 2 of SpharmonicKit has been updated and modified to allow use of a variation of FFTPACK, the freely available library of Fortran routines from NCAR. Use of this modified library is encouraged (though not required) because its FFT and DCT routines are noticeably more efficient than those which come with SpharmonicKit. If the user does not wish to use the modified FFTPACK, it should now be (easily) possible for the user to replace our FFT and DCT routines with their own optimized ones. Further information concerning the modified FFTPACK, the modified software itself, and substituting other FFT and DCT routines, is available here.

Preprints Available

• FFTs for the 2-Sphere - Improvements and Variations

  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 and SGI 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.
  
  
  • D. Healy Jr., D. Rockmore, P. Kostelec and S. Moore, "FFTs for the 2-Sphere - Improvements and Variations," in .pdf (around 1 meg), .ps.Z , (around 1.4 megs) and .ps.gz (around 880 kb) formats. An updated and revised version of this preprint appears in The Journal of Fourier Analysis and Applications 9:4 (2003), pp. 341 - 385.

• Computational Harmonic Analysis for Tensor Fields on the Two-Sphere

  In this paper we describe algorithms for the numerical computation of Fourier transforms of tensor fields on the two-sphere. These algorithms reduce the computation of an expansion on tensor spherical harmonics to expansions in scalar spherical harmonics, and hence can take advantage of recent improvements in the efficiency of computation of scalar spherical harmonic transforms.
  
  
  • P. Kostelec, D. Maslen, D. Rockmore and D. Healy, Jr., "Computational Harmonic Analysis for Tensor Fields on the Two-Sphere", J. Computational Physics 162 (2000), pp. 514 - 535; in .pdf (around 310 kb), .ps (around 385 kb), .ps.Z , (around 180 kb) and .ps.gz (around 130 kb) formats.

The Source Code

Other Possibilities

• Depending on the size of spherical transform one would like to do, it may be more efficient to use the routines provided in Spherepack. This package, developed at NCAR, is a collection of Fortran routines that, among other things, compute spherical harmonic analyses and syntheses.

  Though the spherical transforms in Spherepack are computed using the direct method, the amount of overhead involved in using any non-direct method may make the direct method faster, at least at small enough problem sizes.

• There is also ccSHT: A Fast Parallel Spherical Harmonic Transform, which one might want to investigate.

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

(Visitors to our spherical page)

Return to Fast Fourier Analysis on Groups.