Algorithm 545: An Optimized Mass Storage FFT [C6]
Donald J. Fraser · ACM Transactions on Mathematical Software · 1979
The program is an implementation of the optimal sorting algorithm of the author [8] which allows a base-2 version of the Cooley-Tukey FFT algorithm [2-4] efficient access to a mass store array.Optimal sorting for the mass storage FFT has been determined independently by DeLotto and Dotti [5,6], but in the author's version the emphasis is on "in-place" array modification.This results in slightly higher mass store I/O than the minimum, but requires no additional mass store working space.The method is a logical extension of the work of Singleton [9] and Brenner [1].The program computes in place the discrete Fourier transform of a onedimensional or a multidimensional array.In the one-dimensional case the transform is defined by NI-1 A(J) --SCAL ~ a(j) exp(_ i2~rjJ/N1) for J ffi 0, 1,..., N1 -1 (1) j- 0where SCAL is an arbitrary scaling factor, exp is the exponential function, and i = ,f~-l, the sign of the exponent being either plus or minus, depending on the desired transform.The definition (1) is easily generalized to cover more than one dimension; for example, the two-dimensional ease is given by N2-1 NI--I A(K, J) ffi SCAL ~ Y~ a(j, k) exp(+_ i 2~r(jJ/N1 + kK/N2)) k--0 j--0 for Kffi0,1 ..... N2-1 and Jffi0,1,...,Nl-1.(2)