Bailey's FFT algorithm

[2] 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,[3] some twenty years earlier in 1966.

[5] Here is a brief overview of how the "4-step" version of the Bailey FFT algorithm works: The result (in natural order) is read column-by-column.

Since the operations are performed column-wise and row-wise, steps 2 and 4 (and reading of the result) might include a matrix transpose to rearrange the elements in a way convenient for processing.

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