A PARALLEL FAST FOURIER TRANSFORM

In this paper we discuss the general problem of implementing the multidimensional Fast Fourier Transform algorithm on parallel computers. We show that, on a machine with P processors and fully parallel node communications, the optimal asymptotic scaling behavior of the total computational time with the number of data points, N, given in d dimensions by the formula aN/Plog(N/P)+bN/P^(d-1)/d, can actually be achieved on realistic platforms. As a concrete realization of our strategy, we have produced codes efficiently running on machines of the APE family and on Cray T3E. On the former for asymptotic values of N our codes attain the above optimal result.