AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

45 Minutes

Saarbrücken

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.

gk-sek

--email hidden

passcode not visible

logged in users only