Bailey's FFT algorithm

The Bailey's FFT (also known as a 4-step FFT) is a high-performance algorithm for computing the <a href="/facts/Fast_Fourier_transform/caT7UUCh">fast Fourier transform</a> (FFT). This variation of the <a href="/facts/Cooley%25E2%2580%2593Tukey_FFT_algorithm/03VB7JrC">Cooley–Tukey FFT algorithm</a> was originally designed for systems with hierarchical memory common in modern computers (and was the first FFT algorithm in this so called "out of core" class). The algorithm treats the samples as a two dimensional matrix (thus yet another name, a matrix FFT algorithm) and executes short FFT operations on the columns and rows of the matrix, with a correction multiplication by "<a href="/facts/Twiddle_factor/NSUVICjF">twiddle factors</a>" in between. 
The algorithm got its name after an article by <a href="/facts/David_H._Bailey_(mathematician)/0rhMd4Jz">David H. Bailey</a>, 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, some twenty years earlier in 1966. The algorithm can be considered a radix-
 
 
 
 
 
 n
 
 
 
 
 {\displaystyle {\sqrt {n}}}
 
 FFT decomposition.
Here is a brief overview of how the "4-step" version of the Bailey FFT algorithm works:

<ol><li>The data (in natural order) is first arranged into a matrix.</li>
<li>Each column of a matrix is then independently processed using a standard FFT algorithm.</li>
<li>Each element of a matrix is multiplied by a correction coefficient.</li>
<li>Each row of a matrix is then independently processed using a standard FFT algorithm.</li></ol>
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 <a href="/facts/Matrix_transpose/8wmsagGS">matrix transpose</a> to rearrange the elements in a way convenient for processing. The algorithm resembles a <a href="/facts/Multidimensional_transform/288WFVqy">2-dimensional FFT</a>, a 3-dimensional (and beyond) extensions are known as 5-step FFT, 6-step FFT, etc.
The Bailey FFT is typically used for computing <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">DFTs</a> 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 of elements (when applied to the <a href="/facts/Number-theoretic_transform/ntR67BjE">number-theoretic transform</a>, the datasets of the order of 1012 elements were processed in mid-2000s).

Bailey's FFT algorithm open-in-new

Bailey's FFT algorithm