FFTW is a fast C FFT library. It includes complex, real, symmetric, multidimensional, and parallel transforms, and can handle arbitrary array sizes efficiently.It is typically faster than other freely available FFT implementations, and is even competitive with vendor-tuned libraries (benchmarks are available at the homepage). To achieve this performance, it uses novel code generation and runtime self optimization techniques (along with many other tricks).
