New algorithms for the multidimensional discrete Fourier transform
Lisa Auslander, Ephraim Feig, Shmuel Winograd · IEEE Transactions on Acoustics Speech and Signal Processing · 1983
We exhibit new algorithms for DFT(p; k), the discrete Fourier transform on a k-dimensional data set withppoints along each array, where p is a prime. At a cost of additions only, these algorithms compute DFT(p; k) with (pk- 1)/(p - 1) distinct DFT(p; 1) computations.