Content deleted Content added
Citation bot (talk | contribs) Alter: chapter. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 521/2500 |
m –{{Math-stub}}, +{{Algorithm-stub}}, +{{Signal-processing-stub}} using StubSorter |
||
| (4 intermediate revisions by 3 users not shown) | |||
Line 3:
The '''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 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'''{{sfn|Arndt|2010|p=438}}) and executes short FFT operations on the 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}}
Here is a brief overview of how the "4-step" version of the Bailey FFT algorithm works:
Line 25:
==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
* {{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)}}
Line 33:
{{
{{Signal-processing-stub}}
| |||