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 mat rix factorization technique in a 2-D space and offers a way to do 2-D FFT in both dimensions simultaneously. The computation is greatly redu ced compared to traditional algorithms. This will improve the realizat ion of a 2-D FFT on any kind of computer. However its good parallelism will especially benefit an implementation on a computer with hypercub e 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.