Scientific Computing FAQ: Transforms (FFT, etc) and digital signal processing (DSP)

Transforms (FFT, etc) and digital signal processing (DSP)

FFTs are a standard part of nearly every NA package. For more info, see the: comp.dsp FAQ.

Newsgroup: comp.dsp

See also:

Frigo and Johnson's library of FFT software: FFTW is a C subroutine library for computing the Discrete Fourier Transform (DFT) in one or more dimensions, of both real and complex data, and of arbitrary input size. We believe that FFTW, which is free software, should become the FFT library of choice for most applications. Our benchmarks, performed on on a variety of platforms, show that FFTW's performance is typically superior to that of other publicly available FFT software. Moreover, FFTW's performance is portable: the program will perform well on most architectures without modification.

It is difficult to summarize in a few words all the complexities that arise when testing many programs, and there is no "best" or "fastest" program. However, FFTW appears to be the fastest program most of the time, especially in the multi-dimensional and real-complex cases (Kasparov is the best chess player in the world even though he loses some games). Hence the name, "FFTW," which stands for the somewhat whimsical title of "Fastest Fourier Transform in the West." FFTW is free.

pfftw-0.02 is an experimental fast Fourier transform library for the Pentium and Pentium MMX. pfftw works for inputs whose size is a power of 2 less than or equal to 1024, and it produces an out-of-order output. This release of pfftw supports both single and double precision. pfftw is completely machine-generated, and it was optimized semi-automatically by generating many different codes and selecting the fastest.

DJBFFT is an FFT library tuned for both the Pentium and the UltraSPARC. To give you an idea of how fast this is: Multiplying in R[x]/(x^256-1) in double precision---two DFTs, scaling, multiplication, inverse DFT--- now takes about 14000 UltraSPARC cycles, or 20000 Pentium-II cycles, or 28000 Pentium cycles. I haven't done the roundoff analysis yet, but this convolution should be enough for a product of two 2816-bit integers.