A hybrid parallel M-D FFT algorithm without interprocessor communication

To reduce or eliminate the interprocessor communications, I. Gertner, R. Tolimieri, and their colleagues proposed an M-D fast Fourier transform (FFT) algorithm, called the reduced transform algorithm (RTA). In the present work, the idea of RTA is extended to the M-D Cooley-Tukey (C-T) FFT algorithm and M-D Good-Thomas (G-T) prime factor algorithm. A new implementation strategy for these algorithms that requires no interprocessor communication is discussed. A hybrid algorithm which combines the C-T or G-T algorithm with RTA is also described.<>