高速フーリエ変換

高速フーリエ変換( FFT )は、シーケンスの離散フーリエ変換(DFT) またはその逆 (IDFT)を計算するアルゴリズムです。フーリエ解析は、信号を元の領域 (多くの場合、時間または空間) から周波数領域の表現に変換し、その逆も行います。DFT は、値のシーケンスを異なる周波数の要素に分解することによって得られます。^[1]この操作は多くの分野で役立ちますが、定義から直接計算すると、実用的であるには遅すぎることがよくあります。FFT は、DFT 行列をスパース (ほとんどがゼロ) 因子の積に因数分解することにより、このような変換を迅速に計算します。[ 2 ]その結果^、 DFTの定義を に単純に適用した場合に発生する からの DFT の計算の複雑さを、 nがデータ サイズであるに削減することができます。速度の違いは、特にn が数千または数百万になる可能性のある長いデータ セットの場合に非常に大きくなる可能性があります。丸め誤差がある場合、多くの FFT アルゴリズムは、DFT 定義を直接的または間接的に評価するよりもはるかに正確です。単純な複素数演算から群論や数論まで、公開されている幅広い理論に基づいたさまざまな FFT アルゴリズムが存在します。 ${\textstyle O(n^{2})}$${\textstyle O(n\log n)}$

高速フーリエ変換は、工学、音楽、科学、数学の分野で広く利用されています。基本的な考え方は 1965 年に普及しましたが、一部のアルゴリズムは 1805 年にはすでに考案されていました。 ^[1] 1994 年に、ギルバート ストラングはFFT を「私たちの生涯で最も重要な数値アルゴリズム」と評し、^{[3] [4]} IEEEの雑誌Computing in Science & Engineeringでは 20 世紀のトップ 10 アルゴリズムに選ばれました。^[5]

最もよく知られている FFT アルゴリズムはnの因数分解に依存していますが、 n が素数であっても、すべてのnに対して複雑度を持つ FFT があります。多くの FFT アルゴリズムは、 が1 のn番目の原始根であるという事実のみに依存しているため、数論的変換などの任意の有限体上の類似の変換に適用できます。逆 DFT は DFT と同じですが、指数の符号が逆で、係数が1/ nであるため、任意の FFT アルゴリズムを簡単に適応させることができます。 ${\displaystyle O(n\log n)}$${\textstyle e^{-2\pi i/n}}$

DFT の高速アルゴリズムの開発は、カール・フリードリヒ・ガウスによる 1805 年の未発表の研究 (小惑星パラスとジュノの軌道に関する研究) にまで遡ることができます。ガウスはサンプル観測から軌道を補間したいと考えていました。^{[6] [7]彼の方法は、現代の汎用 FFT アルゴリズムの発明者として一般に認められている}ジェームズ・クーリーとジョン・テューキーが 1965 年に発表したものと非常によく似ています。ガウスの研究はジョセフ・フーリエの 1822 年の結果よりも古いものでしたが、彼はその方法の複雑さを分析せず、最終的には同じ目的を達成するために他の方法を使用しました。

1805年から1965年の間に、FFTのいくつかのバージョンが他の著者によって公開されました。フランク・イェイツは1932年に相互作用アルゴリズムと呼ばれるバージョンを公開しました。これは、アダマール変換とウォルシュ変換の効率的な計算を提供しました。 ^[8]イェイツのアルゴリズムは、実験の統計的設計と分析の分野で今でも使用されています。1942年に、GCダニエルソンとコーネリアス・ランチョスは、フーリエ変換の計算が大きなボトルネックとなる分野であるX線結晶構造解析のDFTを計算するバージョンを公開しました。 ^{[9] [10]}過去の多くの方法は、「対称性」を利用して計算の定数係数を減らすことに焦点を当てていましたが、ダニエルソンとランチョスは、「周期性」を使用して「倍増トリック」を適用して「2倍以上の労力で[ n ]を2倍にする」ことができることに気づきましたが、ガウスのように、これがスケーリングにつながることを発見するための分析は行っていませんでした。^[11]${\textstyle O(n^{2})}$${\textstyle O(n\log n)}$

ジェームズ・クーリーとジョン・テューキーは独立にこれらの初期のアルゴリズムを再発見し^[7]、nが合成数で必ずしも2の累乗ではない場合にも適用可能な、より一般的なFFTを1965年に発表し、スケーリングも解析した。^{[12]テューキーは}ケネディ大統領の科学諮問委員会の会議中にこのアイデアを思いついた。その会議では、ソ連による核実験を外部から取り囲むセンサーを設置することで探知するという議題が議論されていた。これらのセンサーの出力を解析するには、FFTアルゴリズムが必要だった。テューキーとの議論の中で、リチャード・ガーウィンは、国家安全保障の問題だけでなく、ヘリウム3の3次元結晶におけるスピン配向の周期性を決定するという彼の当面の関心事を含む広範囲の問題にもこのアルゴリズムが一般的に適用可能であることを認識した。^[13]ガーウィンはテューキーのアイデアをクーリー（両者ともIBMのワトソン研究所で働いていた）に実行のため渡した。^[14]クーリーとテューキーは6ヶ月という比較的短い期間でこの論文を発表した。^[15]テューキーはIBMで働いていなかったため、このアイデアの特許性は疑われ、アルゴリズムはパブリックドメインとなり、その後の10年間のコンピュータ革命を通じて、FFTはデジタル信号処理に欠かせないアルゴリズムの1つとなった。 ${\textstyle O(n\log n)}$

を複素数とする。DFTは次の式で定義される。 ${\displaystyle x_{0},\ldots ,x_{n-1}}$

${\displaystyle X_{k}=\sum _{m=0}^{n-1}x_{m}e^{-i2\pi km/n}\qquad k=0,\ldots ,n-1,}$

ここで、は1 の 原始n乗根です。${\displaystyle e^{i2\pi /n}}$

この定義を直接評価するには演算が必要です。出力Xk_はn個あり、各出力にはn項 の合計が必要です。FFTとは、演算で同じ結果を計算する方法です。既知のFFTアルゴリズムはすべて演算が必要ですが、より低い複雑度が不可能であるという証明は知られていません。^[16]${\textstyle O(n^{2})}$${\textstyle O(n\log n)}$${\textstyle O(n\log n)}$

FFT による節約を説明するために、データ ポイントに対する複素乗算と加算の回数を考えてみましょう。DFT の合計を評価するには、複素乗算と複素加算が直接必要になりますが、1 による乗算などの単純な演算を排除することで、約 3,000 万回の演算を節約できます。これに対し、基数 2 の Cooley–Tukey アルゴリズム ( nは2 の累乗)では、複素乗算 (この場合も、1 による乗算などの簡略化は無視) と複素加算のみで同じ結果を計算でき、合計で約 30,000 回の演算で済みます。これは、直接評価する場合の 1,000 倍少ない数です。実際には、現代のコンピューターの実際のパフォーマンスは、通常、算術演算の速度以外の要因によって左右され、分析は複雑な問題です (たとえば、Frigo & Johnson、2005 を参照) ^[17]が、からへの全体的な改善は変わりません。 ${\textstyle n=4096}$${\textstyle n^{2}}$${\textstyle n(n-1)}$${\textstyle O(n)}$${\textstyle (n/2)\log _{2}(n)}$${\textstyle n\log _{2}(n)}$${\textstyle O(n^{2})}$${\textstyle O(n\log n)}$

これまでで最も一般的に使用されているFFTは、Cooley-Tukeyアルゴリズムです。これは分割統治アルゴリズムであり、任意の複合サイズのDFTをサイズの小さなDFTに再帰的に分解し、伝統的に回転因子と呼ばれる複素数1の根を乗算します（GentlemanとSande、1966にちなんで）。^[18]${\textstyle n=n_{1}n_{2}}$${\textstyle n_{1}}$${\textstyle n_{2}}$${\displaystyle O(n)}$

この方法（およびFFTの一般的な考え方）は、1965年にCooleyとTukeyが発表した論文^[12]によって普及しましたが、後にこの2人の著者が、1805年頃にCarl Friedrich Gaussが知っていたアルゴリズム[19]（その後、限定された形で何度か再発見された）を共同で独立して再発明していたことが発覚しまし^た[ 1 ^]。

Cooley–Tukey アルゴリズムの最もよく知られた使用法は、各ステップで変換をサイズn/2の 2 つの部分に分割することであり、したがって 2 の累乗のサイズに制限されますが、一般に任意の因数分解を使用できます (これは Gauss と Cooley/Tukey ^{[1]の両方に知られていました)。これらは、それぞれ}基数 2および混合基数の場合と呼ばれます(分割基数 FFTなどの他のバリエーションにも独自の名前があります)。基本的な考え方は再帰的ですが、ほとんどの従来の実装では、明示的な再帰を回避するためにアルゴリズムを再配置します。また、Cooley–Tukey アルゴリズムは DFT をより小さな DFT に分割するため、以下で説明するような DFT の他のアルゴリズムと任意に組み合わせることができます。

Cooley-Tukey 以外の FFT アルゴリズムも存在します。

が互いに素であるとき、中国剰余定理に基づく素因数分解（グッド・トーマス）アルゴリズム（PFA）を使用して、Cooley–Tukey と同様に DFT を因数分解することができますが、回転因子は使用しません。Rader–Brenner アルゴリズム（1976）^[20]は Cooley–Tukey に似た因数分解ですが、純虚数の回転因子を使用し、乗算を減らす代わりに加算が増加し、数値安定性が低下します。これは後に Cooley–Tukey の分割基数版（同じ乗算回数を達成しますが、加算が少なく、精度を犠牲にしません）に置き換えられました。DFT を DFT 以外のより小さな操作に再帰的に因数分解するアルゴリズムには、Bruun アルゴリズムと QFT アルゴリズムがあります。 (Rader–Brenner ^[20]アルゴリズムと QFT アルゴリズムは 2 のべき乗のサイズに対して提案されましたが、一般的な合成nに適応できる可能性があります。Bruun のアルゴリズムは、任意の偶数の合成サイズに適用されます。)特に、 Bruun のアルゴリズムは、FFT を多項式の再帰因数分解として解釈することに基づいています。ここでは、多項式 を、形式およびの実係数多項式に分解します。 ${\textstyle n=n_{1}n_{2}}$ ${\textstyle n_{1}}$${\textstyle n_{2}}$ ${\displaystyle z^{n}-1}$${\displaystyle z^{m}-1}$${\displaystyle z^{2m}+az^{m}+1}$

別の多項式の観点は、ウィノグラードFFTアルゴリズム^{[21] [22]によって利用されており、}円分多項式に因数分解されます。これらの多項式は、係数が1、0、または-1であることが多いため、乗算がほとんど必要ありません（必要な場合でもありません）。そのため、ウィノグラードを使用して乗算が最小限のFFTを取得でき、小さな因数に対する効率的なアルゴリズムを見つけるためによく使用されます。実際、ウィノグラードは、DFTが無理数乗算のみで計算できることを示し、2の累乗のサイズに対する乗算回数の達成可能な下限値につながりました。これは、さらに多くの加算を犠牲にして得られるものであり、ハードウェア乗算器を備えた最新のプロセッサではもはや好ましいトレードオフではありません。特に、ウィノグラードは、素数サイズのFFTに対してRaderのアルゴリズムだけでなくPFAも利用しています。 ${\displaystyle z^{n}-1}$${\displaystyle O(n)}$

Rader のアルゴリズムは、素数n を法とする乗法群の生成元が存在することを利用し、素数サイズnの DFT を(合成) サイズn – 1の巡回畳み込みとして表現します。これは、畳み込み定理を介して 2 つの通常の FFT で計算できます(ただし、Winograd は他の畳み込み方法を使用します)。別の素数サイズの FFT は LI Bluestein によるもので、chirp-z アルゴリズムと呼ばれることもあります。これも DFT を畳み込みとして再表現しますが、今回は同じサイズです (たとえば、 2 の累乗にゼロを詰めて、基数 2 の Cooley–Tukey FFT で評価できます)。これは、次の恒等式によって表されます。

${\displaystyle nk=-{\frac {(kn)^{2}}{2}}+{\frac {n^{2}}{2}}+{\frac {k^{2}}{2 }}.}$

六角形高速フーリエ変換(HFFT) は、配列セット アドレス指定 (ASA) と呼ばれる六角形グリッドの新しいアドレス指定方式を使用して、六角形でサンプリングされたデータの効率的な FFT を計算することを目的としています。

多くのアプリケーションでは、DFTの入力データは純粋に実数であり、その場合、出力は対称性を満たす。

${\displaystyle X_{nk}=X_{k}^{*}}$

そして、この状況のた​​めに効率的なFFTアルゴリズムが設計されてきた（例えば、Sorensen、1987を参照）。^{[23] [24]} 1つのアプローチは、通常のアルゴリズム（例えば、Cooley-Tukey）を採用し、計算の冗長部分を削除して、時間とメモリを約2分の1に節約することです。あるいは、偶数長の実数入力DFTを、半分の長さの複素DFT（実部と虚部は元の実数データの偶数/奇数要素）として表現し、その後に後処理操作を行うこともできます。 ${\displaystyle O(n)}$

かつては、実数入力DFTは離散ハートレー変換（DHT）によってより効率的に計算できると考えられていましたが、その後、同じ入力数に対して対応するDHTアルゴリズム（FHT）よりも少ない演算を必要とする特殊な実数入力DFTアルゴリズム（FFT）が通常見つかると主張されました。^[23] Bruunのアルゴリズム（上記）は、実数入力を利用するために最初に提案された別の方法ですが、人気がありませんでした。

偶数/奇数の対称性を持つ実データの場合、さらに FFT を特殊化できます。この場合、時間とメモリを約 2 倍節約でき、DFT は離散コサイン/サイン変換( DCT / DST ) になります。これらのケースでは、FFT アルゴリズムを直接変更する代わりに、実データの FFT と前処理および後処理 を組み合わせて DCT/DST を計算することもできます。${\displaystyle O(n)}$

コンピュータサイエンスにおける未解決の問題:

高速フーリエ変換アルゴリズムの複雑さの下限はいくらですか? より高速になることはできますか?${\displaystyle O(N\log N)}$

(コンピュータサイエンスにおける未解決の問題)

長年の理論的関心の根本的な問題は、高速フーリエ変換の複雑さと正確な演算回数の下限を証明することであり、多くの未解決の問題が残っています。2のべき乗という単純なケースであっても、DFT が本当に(つまり、次数以上の) 演算を必要とするかどうかは厳密に証明されていませんが、より複雑さが低いアルゴリズムは知られていません。特に、算術演算の回数は通常、このような問題の焦点となりますが、現代のコンピューターの実際のパフォーマンスは、キャッシュやCPU パイプラインの最適化など、他の多くの要因によって決まります。 ${\textstyle \オメガ (n\log n)}$${\displaystyle n\log n}$

Shmuel Winograd (1978)の研究に続いて、 ^[21] FFT に必要な実数乗算の回数の厳しい下限が知られています。2のべき乗の長さの DFT を計算するには、無理数の実数乗算のみが必要であることが示されています。さらに、この回数を達成する明示的なアルゴリズムが知られています (Heideman & Burrus、1986; ^[25] Duhamel、1990 ^[26] )。ただし、これらのアルゴリズムは、少なくともハードウェア乗算器を備えた最新のコンピューターでは、実用的であるには加算が多すぎます (Duhamel、1990; ^[26] Frigo & Johnson、2005)。^[17]${\displaystyle \Theta (n)}$${\textstyle 4n-2\log _{2}^{2}(n)-2\log _{2}(n)-4}$${\displaystyle n=2^{m}}$

必要な加算回数の厳密な下限は知られていないが、アルゴリズムに対するいくつかの制限的な仮定の下で下限は証明されている。1973 年に、Morgenstern [ ^27]は、乗法定数の大きさが制限されているアルゴリズムの加算回数の下限を証明した (これはほとんどの FFT アルゴリズムに当てはまるが、すべてではない)。Pan ( 1986) ^{[28] は、} FFT アルゴリズムの「非同期性」の尺度に上限があると仮定して下限を証明したが、この仮定の一般性は不明である。2 のべき乗nの場合、Papadimitriou (1979) ^[29]は、 Cooley–Tukey アルゴリズムによって達成される複素数加算の回数は、アルゴリズムのグラフに関する特定の仮定の下で最適であると主張した(彼の仮定は、とりわけ、1 の根の加法恒等式が利用されないことを暗示している)。 (この議論は、少なくとも実数の加算が必要であることを意味しますが、複素数の乗算の一部として追加の加算が必要になるため、これは厳密な制限ではありません。) これまでのところ、公開された FFT アルゴリズムでは、2 の累乗nに対して複素数の加算 (またはそれと同等のもの) 未満を達成していません。 ${\displaystyle \Omega (n\log n)}$${\displaystyle \Omega (n\log n)}$${\textstyle n\log _{2}n}$${\textstyle 2N\log _{2}N}$${\textstyle n\log _{2}n}$

3 番目の問題は、実数の乗算と加算の合計回数を最小限に抑えることです。これは「算術計算の複雑さ」と呼ばれることもあります (ただし、この文脈では、考慮されているのは正確な回数であり、漸近的複雑さではありません)。ここでも、厳密な下限は証明されていません。ただし、1968 年以降、2 のべき乗nの最も低い回数は、 n > 1に対して実数の乗算と加算を必要とする分割基数 FFT アルゴリズムによって長い間達成されてきました。これは最近まで削減されました(Johnson and Frigo、2007 年、^[16] Lundy and Van Buskirk、2007 年^[30] )。わずかに大きいカウント（ただし、n ≥ 256の場合の分割基数よりも優れている）は、 n ≤ 512に対して、可能なアルゴリズム（単位係数の乗法因子を持つ分割基数のようなフローグラフ）に対する追加の制約の下で、ブルートフォースで解決可能な理論問題に対する充足可能性への還元によって、証明可能に最適であることが示された（Haynal & Haynal、2011）。^[31]${\textstyle 4n\log _{2}(n)-6n+8}$${\textstyle \sim {\frac {34}{9}}n\log _{2}n}$

FFTアルゴリズムの複雑さを低減または証明する試みのほとんどは、最も単純である通常の複素データの場合に焦点を当ててきました。しかし、複素データFFTは、実数データFFT、離散コサイン変換、離散ハートレー変換などの関連問題のアルゴリズムと非常に密接に関連しているため、これらのうちの1つを改善すると、すぐに他の改善につながります（Duhamel＆Vetterli、1990）。^[32]

上で説明したすべての FFT アルゴリズムは、DFT を正確に計算します (つまり、浮動小数点エラーを無視します)。ただし、計算量が増える代わりにエラーを任意に小さくできる、 DFT を近似的に計算するいくつかの "FFT" アルゴリズムが提案されています。このようなアルゴリズムは、近似エラーと引き換えに速度やその他の特性を向上させます。たとえば、Edelman ら (1999) ^{[33]による近似 FFT アルゴリズムは、}高速多重極法を利用して、並列計算の通信要件を低減します。Guoと Burrus (1996) ^{[34]による}ウェーブレット ベースの近似 FFTは、正確な FFT よりも効率的に、スパースな入力/出力 (時間/周波数の局在) を考慮します。DFT 出力のサブセットを近似的に計算する別のアルゴリズムは、Shentov ら (1995) によるものです。^[35]エデルマンアルゴリズムは、データの圧縮性（スパース性）ではなく、フーリエ行列自体の圧縮性（ランク不足）に基づいているため、スパースデータと非スパースデータの両方で同様に機能します。逆に、データがスパースである場合、つまりn個のフーリエ係数のうちk個だけがゼロでない場合は、計算量を に減らすことができます。これは、確率的近似アルゴリズム（最大のk個の係数を小数点以下数桁で推定する）を使用して、大きなnの例（n = 2 ^{22 ）で}n / k > 32の通常のFFTと比較して実用的な速度向上につながることが実証されています。^[36]${\displaystyle O(k\log n\log n/k)}$

FFT アルゴリズムでは、有限精度浮動小数点演算を使用すると誤差が生じますが、これらの誤差は通常は非常に小さく、Cooley–Tukey などのほとんどの FFT アルゴリズムは、アルゴリズムのペアワイズ加算構造の結果として優れた数値特性を備えています。Cooley –Tukey アルゴリズムの相対誤差の上限はで、ナイーブな DFT 式の場合と比較すると です。^[18]ここで、𝜀はマシン浮動小数点の相対精度です。実際、二乗平均平方根(rms) 誤差はこれらの上限よりもはるかに良好で、Cooley–Tukey とナイーブな DFT の場合のみです (Schatzman、1996)。^[37]ただし、これらの結果は、FFT で使用される回転因子 (つまり、三角関数の値) の精度に非常に敏感であり、不注意な FFT 実装では、たとえば不正確な三角関数の漸化式を使用すると、精度が大幅に低下することも珍しくありません。 Cooley-Tukey 以外の一部の FFT (Rader-Brenner アルゴリズムなど) は、本質的に安定性が低くなります。 ${\textstyle O(\varepsilon \log n)}$${\textstyle O(\varepsilon n^{3/2})}$${\textstyle O(\varepsilon {\sqrt {\log n}})}$${\textstyle O(\varepsilon {\sqrt {n}})}$

固定小数点演算では、FFTアルゴリズムによって蓄積される有限精度誤差はさらに悪化し、Cooley-Tukeyアルゴリズム（Welch、1969）の場合と同様にrms誤差が増加します。^[38]この精度を達成するには、精度の低下を最小限に抑えるためにスケーリングに注意する必要があり、固定小数点FFTアルゴリズムでは、Cooley-Tukeyのような分解の各中間段階で再スケーリングが行われます。 ${\textstyle O({\sqrt {n}})}$

FFT実装の正確性を検証するために、ランダム入力に対する変換の線形性、インパルス応答、および時間シフト特性をチェックする簡単な手順によって、厳密な保証を時間内に得ることができる（Ergün、1995）。^[39]${\textstyle O(n\log n)}$

中間周波数の値は、さまざまな平均化方法によって取得できます。

多次元DFTの記事で定義されているように、多次元DFT

${\displaystyle X_{\mathbf {k} }=\sum _{\mathbf {n} =0}^{\mathbf {N} -1}e^{-2\pi i\mathbf {k} \cdot (\mathbf {n} /\mathbf {N} )}x_{\mathbf {n} }}$

d次元のインデックスベクトルを持つ配列x _{n を}、要素ごとに除算が行われるd個のネストされた合計のセット（各jについて）で変換します。同様に、これはdセットの 1 次元 DFT のシーケンスの合成であり、一度に 1 つの次元に沿って（任意の順序で）実行されます。 ${\textstyle \mathbf {n} =\left(n_{1},\ldots ,n_{d}\right)}$${\textstyle n_{j}=0\ldots N_{j}-1}$${\textstyle \mathbf {n} /\mathbf {N} =\left(n_{1}/N_{1},\ldots ,n_{d}/N_{d}\right)}$

この構成的な観点により、最も単純で最も一般的な多次元 DFT アルゴリズムがすぐに得られます。これは、行-列アルゴリズム (2 次元の場合に続いて、以下参照) と呼ばれます。つまり、 d回の 1 次元 FFTのシーケンスを実行するだけです(上記のアルゴリズムのいずれかを使用)。最初にn ₁次元に沿って変換し、次にn ₂次元に沿って変換します (実際には、順序は任意です)。この方法は、通常の複雑さを持つことが簡単に示されます。ここで、は変換されるデータ ポイントの合計数です。特に、サイズn _1のn / n _{1 回の}変換などがあるため、FFT シーケンスの複雑さは次のようになります。 ${\textstyle O(n\log n)}$${\textstyle n=n_{1}\cdot n_{2}\cdots n_{d}}$

${\displaystyle {\begin{aligned}&{\frac {n}{n_{1}}}O(n_{1}\log n_{1})+\cdots +{\frac {n}{n_{d}}}O(n_{d}\log n_{d})\\[6pt]={}&O\left(n\left[\log n_{1}+\cdots +\log n_{d}\right]\right)=O(n\log n).\end{aligned}}}$

2 次元では、x _{k は}行列として見ることができ、このアルゴリズムは、最初にすべての行 (それぞれ列) の FFT を実行し、結果として得られる変換された行 (それぞれ列) を別の行列としてグループ化し、次にこの 2 番目の行列の各列 (それぞれ行) に対して FFT を実行し、同様に結果を最終結果の行列にグループ化することに対応します。 ${\displaystyle n_{1}\times n_{2}}$ ${\displaystyle n_{1}\times n_{2}}$

2 次元を超える場合、次元を再帰的にグループ化するとキャッシュの局所性に有利になることがよくあります。たとえば、3 次元 FFT では、最初に各固定n _{1について各平面「スライス」の 2 次元 FFT を実行し、次に}n ₁方向に沿って 1 次元 FFT を実行します。より一般的には、漸近的に最適な キャッシュ無視アルゴリズムは、次元を 2 つのグループに再帰的に分割し、それらを再帰的に変換します ( dが偶数でない場合は丸めます) (Frigo および Johnson、2005 を参照)。^[17]それでも、これは行列アルゴリズムの単純なバリエーションであり、最終的には基本ケースとして 1 次元 FFT アルゴリズムのみを必要とし、複雑さは依然としてあります。さらに別のバリエーションは、変換が連続データに対して実行されるように、後続の次元の変換の間に行列転置を実行することです。これは、連続していないデータへのアクセスに非常に時間がかかる、コア外および分散メモリの状況 で特に重要です。${\textstyle (n_{1},\ldots ,n_{d/2})}$${\textstyle (n_{d/2+1},\ldots ,n_{d})}$${\displaystyle O(n\log n)}$

行-列アルゴリズムとは異なる他の多次元 FFT アルゴリズムもありますが、それらはすべて複雑です。おそらく最も単純な非行列 FFT はベクトル基数 FFT アルゴリズムで、これは各ステップで変換次元を基数のベクトルで割る通常の Cooley–Tukey アルゴリズムの一般化です(キャッシュの利点もある可能性があります)。ベクトル基数の最も単純なケースは、すべての基数が等しい場合 (たとえば、ベクトル基数 2 はすべての次元を 2 で割る) ですが、これは必須ではありません。一度に 1 つの非単位基数のみを持つベクトル基数、つまり は、基本的に行-列アルゴリズムです。その他のより複雑な方法には、Nussbaumer (1977) ^{[40]による多項式変換アルゴリズムがあり、これは変換を畳み込みと多項式積の観点から見ています。詳細と参考文献については、Duhamel と Vetterli (1990) [32]}を参照してください。 ${\textstyle O(n\log n)}$${\textstyle \mathbf {r} =\left(r_{1},r_{2},\ldots ,r_{d}\right)}$${\textstyle \mathbf {r} =\left(1,\ldots ,1,r,1,\ldots ,1\right)}$

n ^{2 個の}ノードを持つ球面S ²上の球面調和関数への一般化は、Mohlenkamp ^[41]によって記述され、そのアルゴリズムは複雑性を持つと推測されている（ただし証明されていない）。Mohlenkamp は、libftsh ライブラリで実装も提供している。^[42]複雑性を持つ球面調和関数アルゴリズムは、Rokhlin と Tygert によって記述されている。^[43]${\textstyle O(n^{5/2}\log n)}$${\textstyle O(n^{2}\log ^{2}(n))}$${\textstyle O(n^{2}\log n)}$

高速フォールディング アルゴリズムは、一連の実数または複素スカラー値ではなく、一連のビン化された波形に対して動作することを除いて、FFT に似ています。回転 (FFT では複素位相器による乗算) は、コンポーネント波形の循環シフトです。

ポッツら（2001）でレビューされているように、さまざまなグループが非等間隔データ用の「FFT」アルゴリズムも公開しています。 ^[44]このようなアルゴリズムは、DFT（等間隔データに対してのみ定義されています）を厳密に計算するのではなく、その近似値（非一様離散フーリエ変換、またはNDFT、それ自体は近似的にしか計算されないことが多い）を計算します。より一般的には、スペクトル推定にはさまざまな方法があります。

FFTはデジタル録音、サンプリング、加法合成、ピッチ補正ソフトウェアに使用されます。^[45]

FFTの重要性は、周波数領域での作業が時間領域や空間領域での作業と同様に計算的に実行可能になったという事実に由来しています。FFTの重要な応用には以下が含まれます。^{[15] [46]}

• 高速な大整数乗算アルゴリズムと多項式乗算、
• テプリッツ行列、巡回行列、その他の構造化行列に対する効率的な行列ベクトル乗算、
• フィルタリングアルゴリズム（overlap-addメソッドとoverlap-saveメソッドを参照）
• 離散コサインまたはサイン変換の高速アルゴリズム（例：JPEGおよびMPEG / MP3のエンコードとデコードに使用される高速DCT）
• 高速チェビシェフ近似、
• 差分方程式を解く、
• 同位体分布の計算^[47 ]
• 5G、LTE、Wi-Fi、DSL、その他の最新通信システム向けの直交周波数分割多重 (OFDM) を使用した複雑なデータ シンボルの変調と復調。

FFTの金融、特にオプションの評価における独自の応用は、マルチェロ・ミネナによって開発されました。^[48]

高速フーリエ変換 (FFT) には、その長所にもかかわらず、特に、周波数特性が時間とともに変化する非定常周波数コンテンツを持つ信号を分析する場合に限界があります。FFT はグローバル周波数表現を提供します。つまり、信号の全持続時間にわたって周波数情報を分析します。このグローバルな観点では、FFT はすべての周波数成分が信号全体にわたって存在すると想定するため、信号内の短命または過渡的な特徴を検出することが困難になります。

周波数情報が時間とともに変化する場合は、ウェーブレット変換などの代替変換の方が適している場合があります。ウェーブレット変換では、周波数と時間ベースの両方の情報をキャプチャして、局所的な周波数分析を行うことができます。そのため、重要な情報が信号に短時間現れるアプリケーションに適しています。これらの違いは、FFT が多くのアプリケーションにとって強力なツールである一方で、すべてのタイプの信号分析に最適ではない可能性があることを浮き彫りにしています。

大きなFFT

天文学などの分野でビッグデータが爆発的に増加したため、特定の干渉計計算では512K FFTの必要性が生じています。WMAPやLIGOなどのプロジェクトで収集されたデータには、数百億ポイントのFFTが必要です。このサイズはメインメモリに収まらないため、いわゆるアウトオブコアFFTが活発に研究されています。^[49]

近似FFT

MRIなどのアプリケーションでは、不均一な間隔のグリッドポイントや周波数に対してDFTを計算する必要があります。多重極ベースのアプローチでは、実行時間の増加率で近似量を計算できます。^[50]

グループFFT

FFTは、グループ表現理論を使用して説明および解釈することもでき、これによりさらに一般化できます。非巡回グループを含む任意のコンパクトグループ上の関数は、既約行列要素の基底に関する展開を持ちます。この基底の変更を実行するための効率的なアルゴリズムを見つけることは、研究が活発に行われている分野です。効率的な球面調和関数展開、特定のマルコフ過程の分析、ロボット工学などのアプリケーションがあります。 ^[51]

量子FFT

量子コンピュータ上で整数因数分解を行うショアの高速アルゴリズムには、バイナリベクトルのDFTを計算するサブルーチンがあります。これは、現在量子FFTとして知られている1ビットまたは2ビットの量子ゲートのシーケンスとして実装されており、これは事実上、フーリエ行列の特定の因数分解として実現されたクーリー-テューキーFFTです。これらのアイデアの拡張は現在検討されています。^[52]

FFT 関連のアルゴリズム:

• ビット反転順列
• Goertzelアルゴリズム– 離散フーリエ変換の個々の項を計算する

FFT 実装:

• ALGLIB – 実数/複素数FFT実装を備えたデュアル/GPLライセンスのC++およびC#ライブラリ（他の言語もサポート）
• FFTPACK – 別の Fortran FFT ライブラリ (パブリック ドメイン)
• アーキテクチャ固有:
  • Armパフォーマンスライブラリ^[53]
  • インテル統合パフォーマンスプリミティブ
  • インテルマス カーネル ライブラリ
• CPUやGPU向けの実装は他にもたくさんあり、^[54] C++向けのPocketFFTなどがある。

その他のリンク:

• Odlyzko-Schönhage アルゴリズムはFFT を有限ディリクレ級数に適用します
• シェーンハーゲ・シュトラッセンアルゴリズム– 大きな整数に対する漸近的に高速な乗算アルゴリズム
• バタフライダイアグラム– FFTを説明するために使用されるダイアグラム
• スペクトル音楽（DFT 分析を音楽作曲に適用する）
• スペクトルアナライザ– スペクトル分析を実行するデバイス（通常はDFT経由）
• 時系列
• 高速ウォルシュ・アダマール変換
• 一般化された分配法則
• 最小二乗スペクトル解析
• 多次元変換
• 多次元離散畳み込み
• 高速フーリエ変換望遠鏡

• ブリガム、エルバート・オーラン (1974)。高速フーリエ変換( Nachdr. ed.)。ニュージャージー州エングルウッドクリフス:プレンティス・ホール。ISBN 978-0-13-307496-3。
• Briggs, William; Henson, Van Emden (1995) : The DFT: An Owner's Manual for the Discrete Fourier Transform、SIAM、ISBN 0-89871-342-0。
• Chu, Eleanor; George, Alan (2000): 『FFT ブラック ボックスの内側: シリアルおよびパラレル高速フーリエ変換アルゴリズム』、CRC Press、ISBN 0-8493-0270-6。
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001)。「第30 章: 多項式と FFT」。アルゴリズム入門(第 2 版)。ケンブリッジ (マサチューセッツ州): MIT プレス。ISBN 978-0-262-03293-3。
• Elliott, Douglas F.; Rao, K. Ramamohan (1982)。高速変換:アルゴリズム、分析、アプリケーション。ニューヨーク: Academic Press。ISBN 978-0-12-237080-9。
• Guo, H.; Sitton, GA; Burrus, CS (1994)。「高速離散フーリエ変換」。ICASSP '94 議事録。IEEE 国際音響、音声、信号処理会議。第 3 巻。IEEE。pp . III / 445–III/448。doi :10.1109/ICASSP.1994.389994。ISBN 978-0-7803-1775-8. S2CID  42639206。
• Johnson, Steven G.; Frigo, Matteo (2007 年 1 月)。「より少ない算術演算による修正 Split-Radix FFT」( PDF)。IEEE Transactions on Signal Processing。55 ( 1): 111–119。Bibcode : 2007ITSP ...55..111J。CiteSeerX 10.1.1.582.5497。doi : 10.1109 /TSP.2006.882087。ISSN 1053-587X。S2CID  14772428。2005年 5月26 日にオリジナルからアーカイブ ( PDF) 。 
• Nussbaumer, HJ (1982): Fast Fourier Transform and Convolution Algorithms、第 2 版 (訂正・更新版)、Springer-Verlag、ISBN 3-540-11825-X。
• Press, William H. ; Teukolsky, Saul A. ; Vetterling, William T.; Flannery, Brian P. (2007)。「第 12 章 高速フーリエ変換」。数値レシピ: 科学計算の技術(PDF)。数値レシピ(第 3 版)。ケンブリッジ:ケンブリッジ大学出版局。600 ～ 639 ページ。ISBN 978-0-521-88068-8。
• シングルトン、R. (1969 年 6 月)。「高速フーリエ変換に関する短い参考文献」。IEEE Transactions on Audio and Electroacoustics。17 ( 2): 166–169。doi : 10.1109 /TAU.1969.1162040。ISSN 0018-9278  。(注: 広範な参考文献が含まれています。)
• Prestini, Elena (2004)。応用調和解析の進化: 現実世界のモデル。応用および数値調和解析。ボストン、ベルリン: Springer Media。セクション 3.10: ガウスと小惑星: FFT の歴史。ISBN 978-0-8176-4125-2。
• Van Loan, Charles (1992):高速フーリエ変換の計算フレームワーク、SIAM、ISBN 0-89871-285-8。
• オードリー・テラス(1999):有限群のフーリエ解析とその応用、ケンブリッジ大学出版局、ISBN 0-521-45718-1。(第9章およびその他の章)

• 多項式乗算のための高速フーリエ変換 – 高速フーリエアルゴリズム
• 高速フーリエ変換 - FFT - C++ での FFT プログラミング - Cooley-Tukey アルゴリズム
• オンラインドキュメント、リンク、書籍、コード
• Sri Welaratna、「FFT アナライザーの 30 年」 Wayback Machineで 2014-01-12 にアーカイブ済み、「Sound and Vibration」 (1997 年 1 月、30 周年記念号) – ハードウェア FFT デバイスの歴史的レビュー
• ALGLIB FFT コード – デュアル/GPL ライセンスの多言語 (VBA、C++、Pascal など) 数値解析およびデータ処理ライブラリ
• SFFT: スパース高速フーリエ変換 - MIT のスパース (サブ線形時間) FFT アルゴリズム、sFFT、および実装
• VB6 FFT – ソースコード付きのVB6に最適化されたライブラリ実装
• インタラクティブ FFT チュートリアル – フーリエ変換と FFT 手法の視覚的なインタラクティブな入門
• 時系列のフーリエ解析入門 - 時系列解析におけるフーリエ変換の使い方のチュートリアル