[Fast Fourier transform - Wikipedia](https://en.wikipedia.org/wiki/Fast_Fourier_transform) 高速フーリエ変換（FFT）は、数列の[[離散フーリエ変換]]（DFT）、またはその逆（IDFT）を計算するアルゴリズムである。フーリエ解析は、信号を元の領域（多くの場合、時間または空間）から周波数領域での表現に変換し、その逆もまた可能である。DFTは、一連の値を異なる周波数の成分に分解することで得られる[1]。この演算は多くの分野で有用だが、定義から直接計算すると時間がかかりすぎて実用的でない場合が多い。FFTは、DFT行列を疎な（ほとんどがゼロの）因子の積に因数分解することで、このような変換を高速に計算する。 その結果、DFTの定義を単純に適用した場合に生じる$Oleft(N^{2} Right)$から$O(Nlog N)$ ($N$ はデータサイズ）に計算複雑さを軽減することが可能である。この速度の差は、特にNが数千から数百万に及ぶような長いデータセットの場合、非常に大きくなることがある。丸め誤差がある場合、多くのFFTアルゴリズムは、DFT定義を直接または間接的に評価するよりもはるかに正確です。単純な複素数演算から群論や整数論まで、幅広い理論に基づいたさまざまなFFTアルゴリズムが発表されています。 高速フーリエ変換は、工学、音楽、科学、数学などの分野で広く応用されている。1994年、Gilbert StrangはFFTを「我々の生涯で最も重要な数値アルゴリズム」と評し[3][4]、IEEE誌『Computing in Science & Engineering』の「Top 10 Algorithms of 20th Century」に含まれた[5]。 多くのFFTアルゴリズムは、$e^{-2}pi i/N$が$N$番目の1の冪根であるという事実のみに依存しており、数論変換など、任意の有限体上の類似変換に適用可能である。逆DFTはDFTと同じですが、指数が逆符号で1/N因子なので、どんなFFTアルゴリズムも簡単に適用できます。