2-D FFT ALGORITHM BY MATRIX FACTORIZATION IN A 2-D SPACE

A new 2-D FFT algorithm is described. This algorithm applies a 2-D matrix factorization technique in a 2-D space and offers a way to do 2-D FFT in both dimensions simultaneously. The computation is greatly reduced compared to traditional algorithms. This will improve the realization of a 2-D FFT on any kind of computer. However its good parallelism will especially benefit an implementation on a computer with hypercube architecture. A good arrangement of parallel processors will save a great deal of running time. Furthermore this algorithm can be extended to M-D cases for M > 2.