Fast Fourier transforms for k-space computation

To compute the fast Fourier transform (FFT) of a complex-valued 3-D function, three fundamental input/output management problems need to be addressed: how to store the data, how to access the data, and when to access the data. The natural, or Fortran, order of storage stores three-dimensional data in planes. An improved method is described that uses so called bricks to store the data instead of planes, and uses buffer-in and buffer-out commands to access the data asynchronously. Within these bricks the data is arranged in Fortran order, but each of these bricks may be located in random order on the disk. A section of random-access memory (RAM) is set aside which can hold a sufficiently large number of vectors. An aggregate of these vectors is a ´pencil´ of vectors. The sector of RAM set aside for the maximum size pencil is called the FFT Box. The FFT Box is filled, brick by brick, by calls to disk storage. When filled, the data is rearranged in the FFT Box to be aligned in the direction in which the 1-D FFTs are calculated. This is repeated for each of the components to provide the 3-D FFT result.<>