New Algorithms for the Multidimensional Discrete Fourier Transform

We exhibit new algorithms for DFT(p; k), the discrete Fourier transform on a k- dimensional data set with p points along each array, where p is a prime. At a cost of additions only, these algorithms compute DFT(p; k) with (pk - 1)1 (p - 1) distinct DFT(p; 1) computations. Copyright © 1983 by The Institute of Electrical and Electronics Engineers, Inc.