Jump to content

Bailey's FFT algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Dimawik (talk | contribs) at 01:47, 24 March 2023 (formatting). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
Bailey algorithm (4-step version) for a 16-point FFT

The Bailey FFT (also known as a 4-step FFT) is a high-performance algorithm for computing the fast Fourier transform (FFT) on vector supercomputers. It is designed for systems with hierarchical memory common in modern computers. The Bailey FFT uses a number of techniques to improve the performance:

  • Strictly unit stride, long vector transfers between main memory and external storage
  • A modest amount of scratch space in main memory
  • Well-suited for vector and parallel computation

The Bailey FFT is typically used for computing DFTs of large datasets, such as those used in scientific and engineering applications.

Here is a brief overview of how the "4-step" version of the Bailey FFT algorithm works:

  1. The data (in natural order) is first arranged into a matrix.
  2. Each column of a matrix is then independently processed using a standard FFT algorithm.
  3. Each element of a matrix is multiplied by a correction coefficient.
  4. Each row of a matrix is then independently processed using a standard FFT algorithm.

The result (in natural order) is read column-wise.

The Bailey FFT is a very efficient algorithm, and it has been used to compute FFTs of datasets with billions of elements.