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

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 of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n=2ᵐ</tex> data points is computed in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> passes of the data, and the transformed result is permuted to normal order by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m - 1</tex> additional passes. With buffered input-output, computing can be overlapped with reading and writing of data. Computing time is proportional to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n log₂ n</tex> . 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 in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> passes 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.