SCALABLE I/O: Applications

Contact: Garth Gibson

Fast Fourier Transform (FFT)

We have developped a one dimensional FFT application. It is based on the algorithm descibed in "FFTs in External or Heirarchical Memory" by David H. Bailey. The algorithm consists of four steps. The data set is conceptual turned into a two dimensional n1 by n2 matrix. Each section of length n1 becomes a new row.
  1. Perform n1 FFTs of length n2 on the rows of the matrix.
  2. Scale by multiplying each element Aj,k by e2*pi*i*j*k/n.
  3. Traspose the matrix.
  4. Perform n2 FFTs of length n1 on the rows of the matrix.

An inverse FFT can be performed by substituting IFFT for the FFTs, and negating the exponent in step 2.

In this implementation, steps 2 and 3 have been merged to reduce the number of passes through the data. This procedure allows smaller sections of data to be operated on than the traditional FFT algorithms. It is applied recusively until the amount of memory necessary to perform each individual FFT in steps 1 and 4 is below a user defined limit.

Future development:





© 2018. Legal Info.
Last updated 15 March, 2012