# Computational Complexity - Research Seminar

## Alexey Pospelov: *Fast Fourier transforms: Exhaustive performance in restricted conditions*

Jan. 2, 2011, 10:15 a.m.

E 1 3, Room 415

We present a new algebraic algorithm for computing the DFTs over arbitrary fields. It computes DFTs of infinitely many orders n in O(n log n) algebraic operations, while the complexity of the known FFT algorithms is Omega(n^{1.5}) for such n. Our algorithm is a novel combination of the classical FFT algorithms, and is never slower than any of the latter. As an application we come up with an efficient way of computing DFTs of high orders in finite field extensions which can further boost fast polynomial multiplication. We relate the complexities of the DFTs of special orders with the complexity of polynomial multiplication.