A new series of parallel fast Fourier transform algorithms

Discrete Fourier transform (DFT) has wide application in scientific and technological domains, but its time complexity of direct computation is O(n(2)), limiting greatly its application range. Thus many fast Fourier transform (FFT) algorithms have been 2 developed to reduce the complexity from O(n) to O(nlogn)(In this paper logn denotes log(2)n). But for large n, O(nlogn) is still very high. So multiprocessor systems have been used to speed up the computation of DFT This paper first introduces a new general method to deduce FFT algorithms, then transforms the deduced First Radix-2 Decimation-In-Time FFT algorithm into another parallelizable sequential form, and finally transforms the latter algorithm into a new parallel FFT algorithm, reducing the time complexity of DFT to O(nlogn/p) (where p is the number of processors). Using similar methods, the authors can also design other new parallel 1-D and 2-D FFT algorithms.