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
- An Algorithm for the Machine Calculation of Complex Fourier Series
- The Interaction Algorithm and Practical Fourier Analysis
- Discrete Fourier transforms when the number of data samples is prime
- Some bilinear forms whose multiplicative complexity depends on the field of constants
- Algebras Having Linear Multiplicative Complexities