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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</tex> points along each array, where p is a prime. At a cost of additions only, these algorithms compute DFT(p; k) with (p k - 1)/(p - 1) distinct DFT(p; 1) computations.