Technology Trends: FFT software wins Wilkinson prize

Every four years, Argonne National Laboratory (ANL; Argonne, IL), the National Physical Laboratory (NPL; Teddington, Middlesex, England), and the Numerical Algorithms Group (NAG; Oxford, England) award the Wilkinson Prize for Numerical Software in honor of the contributions made by James Wilkinson to numerical software. Wilkinson, who spent most of his working life at the NPL and regularly visited ANL, is best remembered for his contributions to numerical computation.

This year's $1000 prize, awarded to Matteo Frigo and Steven Johnson of the Massachusetts Institute of Technology (MIT; Cambridge, MA) by Richard Field, chairman of NAG, was for the development of a library of C routines for the computation of the discrete Fourier transform (DFT). Dubbed FFTW, the C subroutine library, available free on the Web at www.fftw.org/download.html, computes the DFT in one or more dimensions of both real and complex data and of arbitrary input size.

To test the software, Frigo and Steven Johnson developed benchFFT, benchmark software that incorporates a number of publicly available FFT implementations, both in C and in FORTRAN, and that measures their performance and accuracy over a range of transform sizes. For those concerned that Frigo and Johnson may have biased the benchmark, the authors have also provided access to benchFFT source code.

"Designed to model systems that repeatedly perform transforms of a particular size, one-time initialization cost is not included in the timing measurements," says Frigo. "This seems to be the most common use for FFT code, especially in cases where performance is important," he adds.

To benchmark the FFT software, the award winners chose a number of readily available FFT implementations including HARM, NAPACK, and QFT (see table). Each software implementation was then computed on a number of different machines including an Alpha EV56 467MHz from Compaq (Houston, TX), an Origin2000 with a 195-MHz MIPS R10000 from SGI (Mountain View, CA), a RS/6000 3BT from IBM (White Plains, NY), a 300-MHz Pentium II (single precision), and an Ultra Enterprise with a 248-MHz UltraSPARC-II CPU from Sun Microsystems (Palo Alto, CA). Results of the benchmarks can be accessed on the Web: www.fftw.org/benchfft/ results/bench_toc.html.