Bailey's FFT algorithm
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:
- Unit stride for the underlying FFT processing is possible, long vector transfers between main memory and external storage
- A modest amount of cache memory is required
- Well-suited for vector and parallel computation
The algorithm got its name after an article by David H. Bailey, FFTs in external or hierarchical memory, published in 1989. In this article Bailey credits the algorithm to W. M. Gentleman and G. Sande who published their paper, Fast Fourier Transforms: for fun and profit, in 1966.[1]
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-by-column.
The Bailey FFT is typically used for computing DFTs of large datasets, such as those used in scientific and engineering applications. The Bailey FFT is a very efficient algorithm, and it has been used to compute FFTs of datasets with billions[citation needed] of elements.
References
- ^ Bailey 1989, p. 2.
Sources
- Bailey, D. H. (March 1989). "FFTs in external or hierarchical memory" (PDF). Journal of Supercomputing. 4 (1). ACM Press: 23–35. doi:10.1145/76263.76288.
 | This mathematics-related article is a stub. You can help Wikipedia by expanding it. |