Parallel Computing of the FFT and of Spectral Filtering with Few to No Complex-Valued Operations

Accurate and faster computation of the Fast Fourier Transform (FFT) using parallel computing is the result of a novel algorithm called FFTpc described in this paper. As opposed to the Cooley-Tukey FFT, the FFTpc uses only real-valued operations until the very last step. Filtering in parallel in the frequency domain is done on data subsets that are processed simultaneously with no data interchange between processors through the main parts of the filtering process. In addition, if the user only requires the magnitude of the transform, the algorithm involves no complex-valued operations at all. Many other novel aspects of the FFTpc and both estimated and actual speedups are reported.