Madagascar development blog

FFTW (the Fastest Fourier Transform in the West) is a famous library implementing an FFT algorithm. It was developed at MIT by Matteo Frigo and Steven G. Johnson and is distributed under a GPL license.

By popular demand, Madagascar's FFT-based programs (such as sffft1 and sffft3) include now an optional support for FFTW. The presence of the FFTW single-precision library is detected during compilation.

The following table shows some peformance measurements (CPU time in seconds for 1,000 complex-valued FFTs using sffft3):

data length	KISS FFT	FFTW
4,096	0.11	0.08
8,192	0.27	0.18
16,384	0.50	0.32
32,768	1.21	0.80
65,536	2.61	1.78

(Photos by Carla Cristina Carvajal Meneses)

The Madagascar school in Austin took place on July 20-21 and was hosted by the Bureau of Economic Geology. More than 40 people attended, representing 15 organizations (11 universities and 4 companies) from 5 different countries. The school materials are available now on the website.

Three years after the first special issue on reproducible research, Computing in Science and Engineering published another special issue this month. The material for this issue comes from the 2011 AMP workshop Reproducible Research: Tools and Strategies for Scientific Computing organized by Randy Leveque, Ian Mitchell, and Victoria Stodden. In an editorial paper, the workshop organizers write:

The principal goal of these discussions and workshops is to develop publication standards akin to both the proof in mathematics and the deductive sciences, and the detailed descriptive protocols in the empirical sciences (the “methods” section of a paper describing the mechanics of the controlled experiment and hypothesis test). Computational science is only a few decades old and must develop similar standards, so that other researchers in the field can independently verify published results.

sffft3 implements a complex-to-complex Fast Fourier Transform (FFT) along an arbitrary axis.

The FFT library that Madagascar uses is KISS FFT, created by Mark Borgerding. KISS stands for Keep it simple, Stupid! KISS FFT may not be as fast as FFTW but it is lightweight and easy to include in the distribution.

The axis= parameter specifies the data axis for performing the transform. The following example from bei/ft1/plane4 (Jon Claerbout's Basic Earth Imaging) shows different forms of the Fourier transform applied to a 2-D dataset.



The algorithm in KISS FFT uses a mixed-radix algorithm, which is most efficient when the input size is N=2^k 3^l 5^m. By default, the input data is padded to the next optimal size, additionally multiplied by 2. To disable this behavior, use opt=n pad=1.

By default, sffft3 applies no scaling in the forward transform and 1/N scaling in the inverse transform. To apply a symmetric 1/√N scaling in both cases, use sym=y.

For a real-to-complex FFT along the first axis, use sffft1.

For a real-to-real Cosine Fourier Transform, use sfcosft.

To apply FFT as a linear operator, try sffft wrapper script.

Previous programs of the month:

• sfdip
• sfderiv
• sfgrey3
• sfspectra
• sfnoise
• sfgraph
• sfclip
• sfagc
• sfenvelope
• sfcontour
• sfsmooth