Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Computational Complexity - Research Seminar

Alexey Pospelov: Fast Fourier transforms: An overview

Jan. 28, 2011, 10:15 a.m.
E 1 3, Room 415

The discrete Fourier transform (DFT) is a linear map that evaluates a given polynomial at powers of a root of unity. An efficient method to compute this transform, known as the Fast Fourier Transform (FFT), was known to Gauss and later rediscovered and extended in the context of digital computing by Cooley and Tukey. The applications of the DFT are very broad, ranging from spectral analysis and data compression to fast integer and polynomial multiplication. The latter involve the DFTs over arbitrary fields. In this talk we give the overview of different FFTs which came in the past 50 years as efficient ways to compute the DFT: Cooley-Tukey's and prime-factor FFT, Rader-Brenner and Bluestein FFT, and dedicated methods to compute the DFTs over finite fields. These algorithms have become important and useful tools in computer science, most notably in signal processing, scientific computing, and symbolic computation.