Discrete Fourier Transform: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(5 intermediate revisions by the same user not shown)
Line 6: Line 6:
== Parameters ==  
== Parameters ==  


<pre>$n$: length of the input data set</pre>
$n$: length of the input data set


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 18: Line 18:
| [[Naive algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Naive algorithm]] || 1965 || $O(n^{2})$ || $O({1})$ || Exact || Deterministic ||   
| [[Naive algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Naive algorithm]] || 1965 || $O(n^{2})$ || $O({1})$ || Exact || Deterministic ||   
|-
|-
| [[Cooley–Tukey algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Cooley–Tukey algorithm]] || 1965 || $O(nlogn)$ || $O(n)$? || Exact || Deterministic || [https://www.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1/S0025-5718-1965-0178586-1.pdf Time]
| [[Cooley–Tukey algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Cooley–Tukey algorithm]] || 1965 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [https://www.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1/S0025-5718-1965-0178586-1.pdf Time]
|-
|-
| [[Rader–Brenner algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Rader–Brenner algorithm]] || 1976 || $O(nlogn)$ || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1162805 Time]
| [[Rader–Brenner algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Rader–Brenner algorithm]] || 1976 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1162805 Time]
|-
|-
| [[Bruun's FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Bruun's FFT algorithm]] || 1978 || $O(nlogn)$ || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1163036/ Time]
| [[Bruun's FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Bruun's FFT algorithm]] || 1978 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1163036/ Time]
|-
|-
| [[Yavne Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Yavne Split Radix FFT algorithm]] || 1968 || $O(nlogn)$ || $O(n)$? || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=1476610 Time]
| [[Yavne Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Yavne Split Radix FFT algorithm]] || 1968 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=1476610 Time]
|-
|-
| [[Gentleman; Morven and Gordon Sande radix-4 algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Gentleman; Morven and Gordon Sande radix-4 algorithm]] || 1966 || $O(nlogn)$ || $O(n)$? || Exact || Deterministic || [http://cis.rit.edu/class/simg716/FFT_Fun_Profit.pdf Time]
| [[Gentleman; Morven and Gordon Sande radix-4 algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Gentleman; Morven and Gordon Sande radix-4 algorithm]] || 1966 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [http://cis.rit.edu/class/simg716/FFT_Fun_Profit.pdf Time]
|-
|-
| [[Bergland; Glenn radix-8 algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Bergland; Glenn radix-8 algorithm]] || 1969 || $O(nlogn)$ || $O(n)$ || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1162043 Time & Space]
| [[Bergland; Glenn radix-8 algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Bergland; Glenn radix-8 algorithm]] || 1969 || $O(n \log n)$ || $O(n)$ || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1162043 Time & Space]
|-
|-
| [[Extended Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Extended Split Radix FFT algorithm]] || 2001 || $O(nlogn)$ || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/917698 Time]
| [[Extended Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Extended Split Radix FFT algorithm]] || 2001 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/917698 Time]
|-
|-
| [[ Von zur Gathen-Gerhard additive FFT (Discrete Fourier Transform Discrete Fourier Transform)| Von zur Gathen-Gerhard additive FFT]] || 1996 || $O(n (logn)$^{2}) || $O(n)$ || Exact || Deterministic || [https://dl.acm.org/doi/10.1145/236869.236882 Time & Space]
| [[ Von zur Gathen-Gerhard additive FFT (Discrete Fourier Transform Discrete Fourier Transform)| Von zur Gathen-Gerhard additive FFT]] || 1996 || $O(n (\log n)$^{2}) || $O(n)$ || Exact || Deterministic || [https://dl.acm.org/doi/10.1145/236869.236882 Time & Space]
|-
|-
| [[Wang-Zhu-Cantor additive FFT (Discrete Fourier Transform Discrete Fourier Transform)|Wang-Zhu-Cantor additive FFT]] || 1988 || $O(n(logn)$^{1.{58}5}) || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1926/ Time]
| [[Wang-Zhu-Cantor additive FFT (Discrete Fourier Transform Discrete Fourier Transform)|Wang-Zhu-Cantor additive FFT]] || 1988 || $O(n(\log n)$^{1.{58}5}) || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1926/ Time]
|-
|-
| [[Gao’s additive FFT (Discrete Fourier Transform Discrete Fourier Transform)|Gao’s additive FFT]] || 2010 || $O(n logn loglogn)$ || $O(n)$ || Exact || Deterministic || [https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613 Time & Space]
| [[Gao’s additive FFT (Discrete Fourier Transform Discrete Fourier Transform)|Gao’s additive FFT]] || 2010 || $O(n logn loglogn)$ || $O(n)$ || Exact || Deterministic || [https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613 Time & Space]
Line 40: Line 40:
|}
|}


== Time Complexity graph ==  
== Time Complexity Graph ==  


[[File:Discrete Fourier Transform - Time.png|1000px]]
[[File:Discrete Fourier Transform - Time.png|1000px]]
== Space Complexity graph ==
[[File:Discrete Fourier Transform - Space.png|1000px]]
== Pareto Decades graph ==
[[File:Discrete Fourier Transform - Pareto Frontier.png|1000px]]

Latest revision as of 09:08, 28 April 2023

Description

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency.

Parameters

$n$: length of the input data set

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Naive algorithm 1965 $O(n^{2})$ $O({1})$ Exact Deterministic
Cooley–Tukey algorithm 1965 $O(n \log n)$ $O(n)$? Exact Deterministic Time
Rader–Brenner algorithm 1976 $O(n \log n)$ $O(n)$? Exact Deterministic Time
Bruun's FFT algorithm 1978 $O(n \log n)$ $O(n)$? Exact Deterministic Time
Yavne Split Radix FFT algorithm 1968 $O(n \log n)$ $O(n)$? Exact Deterministic Time
Gentleman; Morven and Gordon Sande radix-4 algorithm 1966 $O(n \log n)$ $O(n)$? Exact Deterministic Time
Bergland; Glenn radix-8 algorithm 1969 $O(n \log n)$ $O(n)$ Exact Deterministic Time & Space
Extended Split Radix FFT algorithm 2001 $O(n \log n)$ $O(n)$? Exact Deterministic Time
Von zur Gathen-Gerhard additive FFT 1996 $O(n (\log n)$^{2}) $O(n)$ Exact Deterministic Time & Space
Wang-Zhu-Cantor additive FFT 1988 $O(n(\log n)$^{1.{58}5}) $O(n)$? Exact Deterministic Time
Gao’s additive FFT 2010 $O(n logn loglogn)$ $O(n)$ Exact Deterministic Time & Space

Time Complexity Graph

Discrete Fourier Transform - Time.png

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Discrete_Fourier_Transform&oldid=47696"