Two and three dimensional FFTs on highly parallel computers (Q1819919)

Suppose an algorithm is available for a 2-d Fourier transform (FT) on a set of \(N^ 2_ p\) data points where \(N^ 2_ p\) is the number of processing elements. Using this routine and an interleaving technique an algorithm is derived for computing 2-d FTs on a set of \(N^ 2\) data points on computers of SIMD architecture where \(N_ p/N\) is a power of two. 3-d FTs on a set of \(N^ 3\) complex data points are calculated utilizing the 2-d results and the 1-d N-point transform for the third dimension which is computed using a base \('r_ 1+r_ 2'\) fast FT where \(N=r_ 1r_ 2\). A general program is described to calculate 3-d FTs for any values of N and \(N_ p\) where \(N_ p/N\) is a power of two including timings for the runs on an ICL distributed array processor.