Fast Algorithms To Compute Multidimensional Discrete Fourier Transform
Ilya Gertner, Richard Tolimieri · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1989
This paper presents algorithms to com-pute a N -dimensional Discrete Fourier Transform. First existing algorithms are surveyed. Multiplicative symmetrized and orbit exchange algorithm is presented. Then line algorithm to compute Multidi-mensional DFT is derived in two and N -dimensions. The explicit congruences for minimal number of lines covering a mul-tidimensional grid is given, when the data size in one dimension is equal to the power of a prime number.