[Crib-list] Computational Research in Boston Seminar -- Friday, April 1, 2005

[Shirley Entzminger]

COMPUTATIONAL RESEARCH IN BOSTON SEMINAR


DATE:  		Friday, April 1, 2005
LOCATION:  	Building 32, Room 124 (Stata Center)
TIME:  		12:30 PM

TOPIC:		FFTW: The "Fastest Fourier Transform in the West"

SPEAKER:	Steven G. Johnson
 		Massachusetts Institute of Technology

ABSTRACT:

Fast Fourier transforms (FFTs) lie at the heart of many problems in scientific 
computing and engineering, from spectral methods for partial differential 
equations, to digital signal processing, to large-number arithmetic for 
cryptography.  However, despite nearly 40 years of scrutiny, they have proved 
surprisingly resistant to efficient implementation -- FFTs never achieve the 
peak CPU speed except for very small problems, and their historical performance 
has doubled every ~30 months over 40 years, considerably slower than Moore's 
18-month doubling time followed by peak CPU throughput.

In this talk, we outline the historical progression of the understanding of 
fast Fourier transforms and their implementation, from Gauss in 1805 to 
Danielson and Lanczos in 1942 to the digital age that dawned with Cooley and 
Tukey in 1965, to our recent developments of self-optimizing, auto-generated 
FFTs at MIT.  For much of the FFT's history, the focus was on minimizing the 
number of arithmetic operations, from Cooley and Tukey's erroneous assertion 
that radix 3 was optimal to Winograd's demonstration that only O(N) 
multiplications were required for an FFT of length N. Unfortunately, modern 
architectures have divorced performance from simple heuristics like operation 
counts, and the past strategies no longer succeed; the question of the fastest 
algorithm, therefore, has had an ever-changing answer that is increasingly 
difficult to predict.  Instead, we believe that a more stable solution may be 
possible by changing the question: instead of asking what is the best 
algorithm, one should ask what is the smallest collection of simple algorithmic 
fragments whose compositions span the optimal algorithm on as many computer 
architectures as possible.  We describe an implementation of this 
strategy---combining self-optimization, code generation, and recursive 
cache-oblivious algorithms---in the context of FFTW, our free and widely used 
fast Fourier transform (FFT) library (www.fftw.org).


DATE:  		Friday, April 1, 2005

LOCATION:	Building 32, Room 124
  		(Stata Center)

TIME:		12:30 PM

Pizza and beverages will be provided.