A distributed memory algorithm for 3-D FFTs

The present paper begins with a survey of various up-to-date parallel 3-D FFT algorithms and proposes an algorithm for the parallel in-place 3-D FFTs on distributed memory architectures. In the described algorithm, the calculation is accomplished by partitioning the three-dimensional input tensor into subtensors (one subtensor per node). The dimensions of the tensor need not be powers of 2, although some requirements related to the number of nodes need to be fulfilled. mputation of local FFTs is then carried out using the Divide-and-Conquer method and results are combined to obtain the final result using a data partitioning strategy to minimize the communication between the nodes. per is concluded with a comparative discussion of the described algorithm and other parallel 3-D FFT algorithms, with respect to data partitioning, time complexity, communication complexity, memory requirements, how does the shape of the three-dimensional input affect the efficiency of the computation, etc. An implementation of the described algorithm has been tested on an iPSC/860 system and on a 2-D mesh, the Touchstone Delta system.