Bailey's FFT algorithm: Difference between revisions

Revision as of 06:23, 24 March 2023

Revision as of 06:25, 24 March 2023

Line 1:

[[File:Bailey 4-step FFT.svg|thumb|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. ItThis variation of the [[Stockham FFT]] is designed for systems with hierarchical memory common in modern computers. The Bailey FFT uses a number of techniques to improve the performance:

* [[Stride of an array|Unit stride]] for the underlying FFT processing is possible, long vector transfers between main memory and external storage

Line 6:

* Well-suited for vector and parallel computation

The algorithm got its name after an article by [[David H. Bailey (mathematician)|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.{{sfn|Bailey|1989|p=2}} The algorithm can be considered a radix-<math>\sqrt n</math> FFT decomposition.{{sfn|Frigo|Johnson|2005|p=2}}

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