Vectorized mixed radix discrete fourier transform algorithms

Abstract

A number of previous attempts at the vectorization of the fast Fourier transform (FFT) algorithm have fallen somewhat short of achieving the full potential speed of vector processors. The algorithm formulation and implementation described here not only achieves full vector utilization but successfully copes with the problems of hierarchical storage. In the present paper, these techniques are described and extended to the general mixed radix algorithms, prime factoralgorithm (PFA), the multidimensional discrete Fourier transform (DFT), the rectangular transform convolution algorithms, and the Winograd fast Fourier transform algorithm. Some of the methods were used in the Engineering Scientific Subroutine Library for the IBM 3090 Vector Facility. Using this approach, very good and consistent performance was obtained over a very wide range of transform lengths. Copyright © 1987 by The Institute of Electrical and Electronics Engineers, Inc.