A method for computing the fast Fourier transform with auxiliary memory and limited high-speed storage

Abstract

A method is given for computing the fast Fourier transform of arbitrarily large size using auxiliary memory files, such as magnetic tape or disk, for data storage. Four data files are used, two in and two out. A multivariate complex Fourier transform ofn=2^{m}data points is computed inmpasses of the data, and the transformed result is permuted to normal order bym - 1additional passes. With buffered input-output, computing can be overlapped with reading and writing of data. Computing time is proportional ton \log_{2} n. The method can be used with as few as three files, but file passing for permutation is reduced by using six or eight files. With eight files, the optimum number for a radix 2 transform, the transform is computed inmpasses without need for additional permutation passes. An ALGOL procedure for computing the complex Fourier transform with four, six, or eight files is listed, and timing and accuracy test results are given. This procedure allows an arbitrary number of variables, each dimension a power of 2.