Bailey's FFT algorithm: Difference between revisions

Revision as of 01:49, 24 March 2023

Latest revision as of 08:12, 18 November 2024

(40 intermediate revisions by 9 users not shown)

Line 1:

{{Short description|High-performance algorithm}}

[[File:Bailey 4-step FFT.svg|thumb|Bailey algorithm (4-step version) for a 16-point FFT]]

The '''Bailey's FFT''' (also known as a '''4-step FFT''') is a high-performance algorithm for computing the [[fast Fourier transform]] (FFT). onThis vectorvariation supercomputers.of Itthe is[[Cooley–Tukey FFT algorithm]] 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 Baileyalgorithm FFTtreats usesthe samples as a numbertwo ofdimensional techniquesmatrix to(thus improveyet another name, a '''matrix FFT algorithm'''{{sfn|Arndt|2010|p=438}}) and executes short FFT operations on the performance:columns and rows of the matrix, with a correction multiplication by "[[twiddle factor]]s" in between.{{sfn|Hart|Tornaría|Watkins|2010|p=191}}

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'',<ref name="AFIPS 1966 Gentleman and Sande">{{cite conference | first= W.M. |last= Gentleman | first2= G. | last2= Sande | title= Fast Fourier Transforms—For Fun and Profit | conference= Fall Joint Computer Conference, November 7-10, 1966 | book-title= AFIPS Conference Proceedings Volume 29 | year= 1966 | ___location=San Francisco, California | pages=563–578 | url=https://www.cis.rit.edu/class/simg716/FFT_Fun_Profit.pdf }}</ref> some twenty years earlier 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}}

* [[Stride of an array|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 Bailey FFT is typically used for computing DFTs of large datasets, such as those used in scientific and engineering applications.

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

Line 15 ⟶ 12:

# Each row of a matrix is then independently processed using a standard FFT algorithm.

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. The algorithm resembles a [[Multidimensional transform|2-dimensional FFT]], a 3-dimensional (and beyond) extensions are known as '''5-step FFT''', '''6-step FFT''', etc.{{sfn|Hart|Tornaría|Watkins|2010|p=191}}{{sfn|Al Na'mneh|Pan|2007|pp=191-192}}

The result (in natural order) is read column-wise.

The Bailey FFT is typically used for computing [[Discrete Fourier transform|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 of elements (when applied to the [[number-theoretic transform]], the datasets of the order of 10¹² elements were processed in mid-2000s{{sfn|Al Na'mneh|Pan|2007}}).

== See also ==

* [[Row-column FFT algorithm]]

* [[Vector-radix FFT algorithm]]

==References==

{{Reflist}}

==Sources==

* {{cite book | last1 = Bailey | first1 = D. H. | title = Proceedings of the 1989 ACM/IEEE conference on Supercomputing - Supercomputing '89 | chapter = FFTS in external of hierarchical memory | date = March 1989 | publisher = ACM Press | doi = 10.1145/76263.76288 | pages=23–35 | volume = 4 | issue = 1 | isbn = 0897913418 | s2cid = 52809390 | chapter-url = https://www.davidhbailey.com/dhbpapers/fftq.pdf}}

* {{cite journal | last1 = Frigo | first1 = M. | last2 = Johnson | first2 = S.G. | title = The Design and Implementation of FFTW3 | journal = Proceedings of the IEEE | date = February 2005 | volume = 93 | issue = 2 | pages = 216–231 | issn = 0018-9219 | doi = 10.1109/JPROC.2004.840301 | pmid = | bibcode = 2005IEEEP..93..216F | s2cid = 6644892 | url = | citeseerx = 10.1.1.66.3097 }}

* {{cite book | last1 = Hart | first1 = William B. | last2 = Tornaría | first2 = Gonzalo | last3 = Watkins | first3 = Mark | chapter = Congruent Number Theta Coefficients to 10¹² | title = Algorithmic Number Theory | series = Lecture Notes in Computer Science | date = 2010 | volume = 6197 | pages = 186–200 | publisher = Springer Berlin Heidelberg | issn = 0302-9743 | eissn = 1611-3349 | doi = 10.1007/978-3-642-14518-6_17 | isbn = 978-3-642-14517-9 | url = | chapter-url = http://wrap.warwick.ac.uk/41654/1/WRAP_Hart_0584144-ma-270913-congruent.pdf }}

* {{cite journal | last1 = Al Na'mneh | first1 = Rami | last2 = Pan | first2 = W. David | title = Five-step FFT algorithm with reduced computational complexity | journal = Information Processing Letters | date = March 2007 | volume = 101 | issue = 6 | pages = 262–267 | issn = 0020-0190 | doi = 10.1016/j.ipl.2006.10.009 | pmid = | url = }}

* {{cite book | first1 = Jörg | last1 = Arndt | date = 1 October 2010 | title = Matters Computational: Ideas, Algorithms, Source Code | publisher = Springer Science & Business Media | pages = 438–439 | isbn = 978-3-642-14764-7 | oclc = 1005788763 | chapter-url = https://books.google.com/books?id=HsRHS6u7e80C&pg=PA438 | chapter = The Matrix Fourier Algorithm (MFA)}}

[[Category:FFT algorithms]]

{{Algorithm-stub}}

The Bailey FFT is a very efficient algorithm, and it has been used to compute FFTs of datasets with billions of elements.

{{Signal-processing-stub}}