Lesson plan
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- \sqrt n FFT decomposition.
Article summary
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- \sqrt n FFT decomposition.
Key claims
- publication date: 1989 — source: Wikipedia · confidence 0.95
- publication date: 1966 — source: Wikipedia · confidence 0.95
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- The record states that the publication date is "1989". What evidence would count against this claim?
- The record states that the publication date is "1966". What evidence would count against this claim?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
- Wikipedia https://en.wikipedia.org/w/index.php?oldid=1374298660
Key claims and bibliography are generated from the same tracked claims and sources as the article page.