Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

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.