An Efficient Two-Dimensional FFT Algorithm

A new version of the radix-2 row-column method for computing two-dimensional fast Fourier transforms is proposed. It uses a ``multiple vector´´ FFT algorithm to compute the transforms of all the columns in an array simultaneously while avoiding all trivial multiplications. The minicomputer implementation of the algorithm runs faster than the 2 × 2 vector radix FFT algorithm. Analysis of the numbers of complex additions and multiplications required indicate that implementations of the radix-4 row-column FFT and 4 × 4 vector radix FFT on the same minicomputer would run slower than the multiple vector implementation.