Parallel Compact FFT s for Real Sequences
Richard B. Pelz · SIAM Journal on Scientific Computing · 1993
Eight algorithms for the in-place, compact, fast Fourier transform (FFT) of real and conjugate-symmetric sequences are presented for single instruction multiple data (SIMD) and multiple instruction multiple data (MIMD) distributed-memory multiprocessors. The “conditional ordering” is introduced for conjugate-symmetric sequences as the natural ordering that leads to minimal communication costs. For a transform of a real, naturally ordered, input sequence of length N distributed evenly across P processors, $2 + \log _2 P$ nearest neighbor communication exchanges of $\tfrac{1}{2}N/P$ contiguous elements (i-cycles) are necessary. For a transform of a conjugate-symmetric, conditionally ordered input sequence, $1 + \log _2 P$i-cycles are necessary. In all cases the computational complexity is $\tfrac{5}{2}N/ P\log _2 N$, and there are no extra memory requirements. The algorithms require about half the communication of a parallel FFT of a real sequence that involves a complex FFT and pre- or postprocessing. Communication complexity is based on the hypercube topology; the algorithms, however, can be implemented on general connection topologies. Some of the schemes are implemented on an nCUBE/2 MIMD multiprocessor, and timings are given.