Row-Column versus Vector-Radix: A Comparative Case Study of Two Parallel 2D Fourier Transform Algorithms.

Abstract

The parallelization of two different methods to compute the complex discrete two-dimensional Fourier transform is investigated. The row-column method uses successive one-dimensional Fourier transforms along each dimension whereas the vector-radix method recursively computes two-dimensional Fourier transforms of lower sizes. Each method is examined with respect to independent computational parts that can be done in parallel. Performance results on a distributed memory computer with up to 16 processors are given demonstrating that the vector-radix method is attractive compared to the more widely used row-column method.