高速フーリエ変換
p = 0, 1, ..., P − 1 と r = 0, 1, ..., Q − 1 について f 1 ( p , r ) = exp  ( − 2 π i p r P Q ) ∑ q = 0 Q − 1 f ( q P + p ) exp  ( − 2 π i r q Q ) {\displaystyle f_{1}(p,r)=\exp \left(-2\pi i{\frac {pr}{PQ}}\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)}
を計算する。これは、Q次の離散フーリエ変換 ∑ q = 0 Q − 1 f ( q P + p ) exp  ( − 2 π i r q Q ) {\displaystyle \sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)}
の実行と、回転因子 exp(−2πipr/PQ) の掛け算を、全ての p, r の組(PQ = N 通り)に対して行うことと見ることができる。
フーリエ変換
離散フーリエ変換 (DFT)
Butterfly diagram(英語版)
Overlap–add method(英語版) / Overlap–save method(英語版)
Spectral music(英語版)
スペクトラムアナライザ
FFTPACK
時系列
Math Kernel Library
ショーンハーゲ・ストラッセン法(乗算アルゴリズム(英語版))
Sparse Fourier transform(英語版) ※ (高速)スパース・フーリエ変換(SFT)