A fast Fourier transformation algorithm for parallel computers

A new algorithm is presented for using the fast Fourier transform (FFT) in a very efficient mode. This algorithm is ideal for a parallel computer such as the ICL Distributed Array Processor (DAP), though it can be used with benefit on any serial computer. For a two- or three-dimensional electron density Fourier map the Fourier coefficients are arranged in a one-dimensional vector form of the chosen length and the whole map is obtained by a single FFT operation. To obtain a higher density of calculated points in the map a number of FFT operations is required, each entailing a phase modification of the one-dimensional Fourier coefficients. A three-dimensional map using 1429 crystal reflections and giving the density at 32768 points takes roughly 2 s in the ICL DAP.