Fast Evaluation of Multidimensional DFT

The computation of the multidimensional discrete Fourier transform (DFT) using the discrete Radon transform (DRT) is reducible to the computation of finitely many one-dimensional DFTs. The paper proposes an algorithm for the computation of the DFT of a $d$-dimensional array of $N^d$ points using a minimum number of one-dimensional DFTs $\psi(N)N^{d-1}$. The behaviour of the function $\psi$ is determined by the arithmetic properties of the number $N$, and it is desirable to choose a prime $N$.