Bailey's FFT algorithm
Appearance

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:
- The data (in natural order) is first arranged into a matrix.
- Each column of a matrix is then independently processed using a standard FFT algorithm.
- Each element of a matrix is multiplied by a correction coefficient.
- 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.