Bailey's FFT algorithm

Bailey's FFT (also known as a 4-step FFT) is a high-performance algorithm for computing the fast Fourier transform (FFT). This variation of the Cooley–Tukey FFT algorithm was originally designed for systems with hierarchical memory, as is common in modern computers, and was the first FFT algorithm in this "out of core" class. The algorithm treats the samples as a two dimensional matrix (thus another name, a matrix FFT algorithm) and executes short FFT operations on the columns and rows of the matrix, with multiplication by correction "twiddle factors" in between.

The algorithm is named 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, more than two decades earlier. The algorithm can be considered a radix-${\displaystyle {\sqrt {n}}}$ FFT decomposition.

Algorithm

Let ${\displaystyle n=n_{1}n_{2}}$ be the transform size, and let the input data be represented as a ${\displaystyle n_{1}\times n_{2}}$ matrix. Bailey's four-step FFT consists of the following steps:

1. Perform ${\displaystyle n_{1}}$ independent ${\displaystyle n_{2}}$ point FFTs on the input matrix.
2. Multiply each resulting matrix element ${\displaystyle A_{jk}}$ by the corresponding twiddle factor ${\displaystyle e^{\pm 2\pi ijk/n}}$, where the sign depends on the convention used for the transform.
3. Transpose the resulting ${\displaystyle n_{1}\times n_{2}}$ matrix to get a ${\displaystyle n_{2}\times n_{1}}$ matrix.
4. Perform ${\displaystyle n_{2}}$ independent ${\displaystyle n_{1}}$ point FFTs on the transposed matrix.

When the component FFTs produce their outputs in natural order, the resulting transform is also in natural order and does not require a separate bit-reversal permutation. Bailey noted that ${\displaystyle n_{1}}$ and ${\displaystyle n_{2}}$ don't need to be equal, although on many systems the algorithm is the most efficient when they are chosen as close as possible to ${\displaystyle {\sqrt {n}}}$.

The algorithm resembles a 2-dimensional FFT; three-dimensional and higher dimensional extensions are known as 5-step FFT, 6-step FFT, etc.

Applications

The Bailey FFT is typically used for computing DFTs of large datasets, such as those used in scientific and engineering applications. It has been used to compute FFTs of datasets with billions of elements; when applied to the number-theoretic transform, datasets on the order of 10¹² elements were processed in the mid-2000s.

Memory locality

The Bailey FFT's four step decomposition improves memory locality by replacing one large transform with groups of smaller transforms that can be performed on contiguous portions of data. If the component transforms fit within a faster level of a memory hierarchy, then the accesses during those transforms can be served from that level rather than from a slower level of memory.

Likewise, the matrix transpose rearranges the data so that the second set of component transforms can be performed with better access patterns. The original intention of Bailey was to develop a method for systems in which the complete dataset could not be held in fast memory, which allows the transform to be organized around transfers between levels of a hierarchical memory system.

See also

• Row-column FFT algorithm
• Vector-radix FFT algorithm

References

Sources

• Bailey, D. H. (March 1989). "FFTS in external of hierarchical memory" (PDF). Proceedings of the 1989 ACM/IEEE conference on Supercomputing - Supercomputing '89. Vol. 4. ACM Press. pp. 23–35. doi:10.1145/76263.76288. ISBN 0897913418. S2CID 52809390.
• Frigo, M.; Johnson, S.G. (February 2005). "The Design and Implementation of FFTW3". Proceedings of the IEEE. 93 (2): 216–231. Bibcode:2005IEEEP..93..216F. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301. ISSN 0018-9219. S2CID 6644892. {{cite journal}}: Cite uses deprecated parameter |citeseerx= (help)
• Hart, William B.; Tornaría, Gonzalo; Watkins, Mark (2010). "Congruent Number Theta Coefficients to 10¹²" (PDF). Algorithmic Number Theory. Lecture Notes in Computer Science. Vol. 6197. Springer Berlin Heidelberg. pp. 186–200. doi:10.1007/978-3-642-14518-6_17. eISSN 1611-3349. ISBN 978-3-642-14517-9. ISSN 0302-9743.
• Al Na'mneh, Rami; Pan, W. David (March 2007). "Five-step FFT algorithm with reduced computational complexity". Information Processing Letters. 101 (6): 262–267. doi:10.1016/j.ipl.2006.10.009. ISSN 0020-0190.
• Arndt, Jörg (1 October 2010). "The Matrix Fourier Algorithm (MFA)". Matters Computational: Ideas, Algorithms, Source Code. Springer Science & Business Media. pp. 438–439. ISBN 978-3-642-14764-7. OCLC 1005788763.