FFT algorithms and their adaptation to parallel processing (Q1124776)

The parallelization of sequential fast Fourier transforms (FFTs) on high-performance multiprocessor computers has received much attention during the last decade. Based on the concept of index-digit permutation and associated binary address based notation the paper puts the various ideas which have appeared in FFT literature in a common framework. Moreover, three new distributed-memory parallel FFTs along with communication complexity results are presented. The proposed algorithms show alternative ways of designing parallel FFT algorithms with feature reduced communication cost and further flexibility in the choices of data mappings.