Cooley–Tukey Fast Fourier Transform algorithm

E373658

Fast Fourier Transform algorithm divide-and-conquer algorithm numerical algorithm signal processing algorithm

The Cooley–Tukey Fast Fourier Transform algorithm is a widely used, efficient method for computing the discrete Fourier transform that revolutionized digital signal processing and numerical analysis.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (6)

Label	Occurrences
Cooley–Tukey Fast Fourier Transform algorithm canonical	1
FFT	1
Fast Fourier Transform	1
fast Fourier transform	1
mixed-radix Cooley–Tukey FFT	1
radix-2 Cooley–Tukey FFT	1

How this entity was disambiguated

This entity first appeared as the object of triple T3600027 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Cooley–Tukey Fast Fourier Transform algorithm
Context triple: [John W. Tukey, coDeveloped, Cooley–Tukey Fast Fourier Transform algorithm]

A. FFT
FFT is the ICAO airline designator used in aviation to identify Frontier Airlines in flight plans and air traffic control communications.
B. Fourier
Fourier is a French surname most famously associated with Jean-Baptiste Joseph Fourier, the mathematician and physicist known for developing Fourier analysis and Fourier series.
C. Berlekamp’s algorithm for factoring polynomials over finite fields
Berlekamp’s algorithm for factoring polynomials over finite fields is a foundational deterministic method in computational algebra that efficiently decomposes polynomials into irreducible factors over finite fields and underpins many modern algorithms in coding theory and cryptography.
D. Marzullo's algorithm
Marzullo's algorithm is a method for selecting the most likely correct time interval from multiple, possibly conflicting time sources, commonly used in clock synchronization systems.
E. Berlekamp–Massey algorithm
The Berlekamp–Massey algorithm is a key algorithm in coding theory and cryptography used to efficiently determine the shortest linear feedback shift register that generates a given binary sequence.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Cooley–Tukey Fast Fourier Transform algorithm
Target entity description: The Cooley–Tukey Fast Fourier Transform algorithm is a widely used, efficient method for computing the discrete Fourier transform that revolutionized digital signal processing and numerical analysis.

A. FFT
FFT is the ICAO airline designator used in aviation to identify Frontier Airlines in flight plans and air traffic control communications.
B. Fourier
Fourier is a French surname most famously associated with Jean-Baptiste Joseph Fourier, the mathematician and physicist known for developing Fourier analysis and Fourier series.
C. Berlekamp’s algorithm for factoring polynomials over finite fields
Berlekamp’s algorithm for factoring polynomials over finite fields is a foundational deterministic method in computational algebra that efficiently decomposes polynomials into irreducible factors over finite fields and underpins many modern algorithms in coding theory and cryptography.
D. Marzullo's algorithm
Marzullo's algorithm is a method for selecting the most likely correct time interval from multiple, possibly conflicting time sources, commonly used in clock synchronization systems.
E. Berlekamp–Massey algorithm
The Berlekamp–Massey algorithm is a key algorithm in coding theory and cryptography used to efficiently determine the shortest linear feedback shift register that generates a given binary sequence.
F. None of above. chosen

Statements (48)

Predicate	Object
instanceOf	Fast Fourier Transform algorithm ⓘ divide-and-conquer algorithm ⓘ numerical algorithm ⓘ signal processing algorithm ⓘ
appliesTo	complex-valued sequences ⓘ real-valued sequences ⓘ
assumes	periodicity of discrete-time signals in DFT formulation ⓘ
basedOn	divide-and-conquer strategy ⓘ
category	Fourier analysis ⓘ computational mathematics ⓘ
computes	discrete Fourier transform ⓘ inverse discrete Fourier transform ⓘ
enables	efficient circular convolution ⓘ fast correlation computation ⓘ
hasKeyOperation	complex additions ⓘ complex multiplications ⓘ
hasTimeComplexity	O(N log N) ⓘ
hasVariant	decimation-in-frequency FFT ⓘ decimation-in-time FFT ⓘ mixed-radix Cooley–Tukey FFT ⓘ linked to: Cooley–Tukey Fast Fourier Transform algorithm radix-2 Cooley–Tukey FFT ⓘ linked to: Cooley–Tukey Fast Fourier Transform algorithm radix-4 Cooley–Tukey FFT ⓘ
historicallySignificantIn	digital signal processing revolution ⓘ numerical analysis ⓘ
improvesOn	direct discrete Fourier transform computation ⓘ
influenced	modern digital communications systems ⓘ real-time signal processing applications ⓘ
introducedInPublicationYear	1965 ⓘ
isFoundationFor	CUDA FFT implementations ⓘ FFTW library design ⓘ Intel MKL FFT routines ⓘ many FFT software libraries ⓘ
namedAfter	James W. Cooley ⓘ John W. Tukey ⓘ
publishedIn	Mathematics of Computation ⓘ
requires	bit-reversal permutation in some implementations ⓘ
supports	composite transform lengths ⓘ power-of-two transform lengths ⓘ
typicalDFTComplexity	O(N^2) ⓘ
usedIn	audio compression ⓘ convolution via frequency domain multiplication ⓘ digital signal processing ⓘ image processing ⓘ numerical solutions of partial differential equations ⓘ spectral analysis ⓘ
uses	butterfly computation pattern ⓘ radix decomposition of transform length ⓘ twiddle factors ⓘ

How these facts were elicited