On computing the discrete Fourier transform
Shmuel Winograd · Mathematics of Computation · 1978
A new algorithm for computing the Discrete Fourier Transform is described. The algorithm is based on a recent result in complexity theory which enables us to derive efficient algorithms for convolution. These algorithms are then used to obtain the new Discrete Fourier Transform algorithm.