Zweidimensionale Schnelle Fourier-Transformation auf massiv-parallelen Rechnern.




We analyze the parallelization of three different methods to compute the complex, discrete, two-dimensional Fourier transform. The row-column method uses one-dimensional Fourier transforms along each dimension of the data which should be transformed. The vector-radix method computes a two-dimensional transform by recursively calculating two-dimensional transforms of lower sizes. In the special case of a (p times p)-transform, with a prime p, a method due to Gertner can be used. Initially, this method determines Radon transforms and subsequently performs one-dimensional Fourier transforms on the results of the Radon transforms. The row-column method as well as the vector-radix method are implemented up to size 512 times 512 points with radix-2. For the method due to Gertner this quantity increases to 619 times 619. Each method is examined with respect to computational parts which are independent of one another and consequently can be done in parallel. We show how these three methods can be implemented on a specific massively parallel computer. We use the Intel iPSC860 and offer timing results on this hypercube with 32 nodes.