A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform of a sequence, or its inverse, converting a signal between its original domain, often time or space, and a representation in the frequency domain. It works by factorizing the discrete Fourier transform's matrix into a product of mostly-zero, sparse factors, which reduces the computational cost of the transform from O(n squared), the cost of applying the definition directly, to O(n log n). The ideas underlying it date as far back as an unpublished 1805 method by Carl Friedrich Gauss, but the algorithm was popularized in its modern form in 1965 by James Cooley and John Tukey. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Time ComplexityO(n log n), versus O(n squared) for direct evaluation of the discrete Fourier transform. 1 Credited ToBasic ideas trace to an unpublished 1805 method by Carl Friedrich Gauss; popularized in modern form by James Cooley and John Tukey in 1965. 1 Classification
Design Technique Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Connections
Credited To
Source Wikipedia: Fast Fourier Transform
Source Wikipedia: Fast Fourier Transform
In Field
Source Wikipedia: Fast Fourier Transform
Invented By
Verified en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm: "Cooley and Tukey subsequently published their joint paper" introducing the modern Cooley-Tukey Fast Fourier Transform algorithm.
Verified en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm: "Cooley and Tukey subsequently published their joint paper" introducing the modern Cooley-Tukey Fast Fourier Transform algorithm.
Uses Design Technique
Sources
1. Wikipedia: Fast Fourier Transform
Wikimedia FoundationLead section
from O(n^2), which arises if one simply applies the definition of DFT, to O(n log n), where n is the length of the sequence
Body, history
The basic ideas were popularized in 1965 by James Cooley and John Tukey, though earlier algorithms dated back to 1805 by Carl Friedrich Gauss.
- FFT/Cooley-Tukey: "This is a divide-and-conquer algorithm that recursively breaks down a DFT"
Credited To: James Cooley, History section
published in 1965 by James Cooley and John Tukey, who are generally credited for the invention of the modern generic FFT algorithm
Credited To: John Tukey, History section
published in 1965 by James Cooley and John Tukey, who are generally credited for the invention of the modern generic FFT algorithm
In Field: Algorithms and Complexity Theory, Lead sentence
fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT), or its inverse (IDFT), of a sequence.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.