An efficient algorithm for the computation of the multidimensional discrete Fourier transform (Q1307712)

The authors propose a new algorithm for the multidimensional discrete Fourier transform based on the Cooley decimation in time method by using an appropriate indexing scheme and the tensor product properties. Thus, the number of multiplications is significantly reduced while the number of additions is almost the same as in the classical multidimensional FFT algorithm. Consequently, the computation time is reduced. Moreover, the simple matrix form of the algorithm allows the convenient implementation on various multiprocessor architectures.