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.

Cited by 613 works. doi:10.1090/s0025-5718-1978-0468306-4 Open-access PDF

Authors

References