Overview
The Fast Fourier Transform splits a DFT into smaller transforms, combines even and odd components, and reduces the usual quadratic work to O(n log n) for suitable sizes.
FoundationSource checked
Fast Fourier Transform
Computes the discrete Fourier transform efficiently by reusing symmetry and subproblem structure.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Numerical Methods
- Difficulty
- Advanced
- Family
- Divide and Conquer
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 5
- Code example
- Not ready
- Visualization
- Ready
- Aliases
- FFT
Core Concepts
DFTdivide and conquertwiddle factorfrequency domain
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)
When to Use
- Use it for frequency analysis, convolution, polynomial multiplication, or signal processing.
- Use it when input sizes and boundary assumptions fit an FFT implementation.
- Use real-valued or specialized FFT variants when the data structure allows.
When Not to Use
- Avoid it for very small inputs where setup costs dominate.
- Avoid it when sampling assumptions make frequency interpretation misleading.
- Avoid circular convolution artifacts unless padding or boundary handling is correct.
What It Does
- Transforms samples into frequency components
- Reuses subproblem results
Use Cases
- Audio analysis
- Fast convolution
- Frequency-domain filtering
Inputs
- Evenly spaced samples
Outputs
- Frequency-domain coefficients
Key Formulas (1)
DFT decomposition
DFT(x) = combine(DFT(even samples), DFT(odd samples))
DFT(x) = combine(DFT(even samples), DFT(odd samples))Splits a transform into smaller transforms that can be reused.
Pseudocode
- 1.Split samples into even and odd positions
- 2.Recursively transform each half
- 3.Combine paired frequency results with twiddle factors
- 4.Return the full frequency array
Canonical Example
- Input
- equation = x^2 - 9 = 0 or matrix system Ax = b
- Output
- approximate numeric solution
- Explanation
- Fast Fourier Transform: The method iteratively or algebraically approximates the requested mathematical result.
Implementation Notes
- Use established FFT libraries for performance and numerical reliability.
- Track transform length, normalization, and real-versus-complex input conventions.
- Pad inputs when using multiplication in the frequency domain for linear convolution.
Common Pitfalls
- Forgetting normalization conventions between forward and inverse transforms.
- Misinterpreting frequency bins for the sampling rate.
- Failing to zero-pad when using FFT for linear convolution.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow samples splitting and recombining through butterfly stages.
Step 1 of 4: Split samples into even and odd positions
fft-butterflyNotes
FFT names a family of algorithms; radix-2 Cooley-Tukey is common but not the only variant.
Sources (2)
What each reference supports for this entry.
Cooley-Tukey FFT paper
PaperOriginal fast Fourier transform paper introducing the divide-and-conquer FFT structure.
Open sourceMatrix Computations
BookReference text for numerical linear algebra, matrix factorizations, SVD, and eigenvalue methods.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byShort-Time Fourier Transform
Signal Processing · Extended
The short-time Fourier transform applies Fourier transforms to overlapping windowed signal frames.
Compare with thisRelationships
View full relationship pageImproves onDiscrete Fourier Transform
FFT computes the same transform more efficiently for suitable sizes.
Prerequisite ofInverse Fast Fourier Transform
The inverse FFT uses the same divide-and-conquer transform structure.
Related Algorithms
Tags
Numerical MethodsFrequency DomainDivide and ConquerSignal Processing