Bailey's FFT algorithm
 | This article is actively undergoing a major edit for a little while. To help avoid edit conflicts, please do not edit this page while this message is displayed. This page was last edited at 01:45, 24 March 2023 (UTC) (2 years ago) – this estimate is cached, . Please remove this template if this page hasn't been edited for a significant time. If you are the editor who added this template, please be sure to remove it or replace it with {{Under construction}} between editing sessions. |
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.