Cooley-Tukey FFT on the Connection Machine (Q1195705)

The objective of this paper is an efficient adaptation of the Cooley- Tukey fast Fourier transform (FFT) to multiprocessors interconnected by a Boolean cube network. The implementation is designed to make effective use of the communications bandwidth, the memory bandwidth, and the storage requirements with precomputed twiddle factors. The algorithms have been implemented on the connection machine systems CM-200 with 2048 floating-point processors. Performance data are provided for one- and two-dimensional FFT.