高速フーリエ変換
上記の説明で、 N = Q k ( P = Q k − 1 ) {\displaystyle N=Q^{k}(P=Q^{k-1})} の場合、N = Q 個のデータ f ( q Q k − 1 + p ) {\displaystyle f(qQ^{k-1}+p)} から、N = Q 個の計算結果
f 1 ( p , r ) = exp  ( − 2 π i p r Q k ) ∑ q = 0 Q − 1 f ( q Q k − 1 + p ) exp  ( − 2 π i r q Q ) {\displaystyle f_{1}(p,r)=\exp \left(-2\pi i{\frac {pr}{Q^{k}}}\right)\sum _{q=0}^{Q-1}f(qQ^{k-1}+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)}
を計算する場合に、メモリの節約のため、0 ≤ q ≤ Q − 1 と 0 ≤ r ≤ Q − 1 を利用し、計算結果 f 1 ( p , r ) {\displaystyle f_{1}(p,r)} を元データ f ( r Q k − 1 + p ) {\displaystyle f(rQ^{k-1}+p)} のあった場所に格納することが多い。
今後記述を追加の予定
Henri J. Nussbaumer: "Fast Fourier Transform and Convolution Algorithms",2nd Ed.,Springer-Verlag, ISBN 978-3-540-11825-1 (1982年).
E.Oran Brigham:「高速フーリエ変換」、科学技術出版社 (1985年).
Henri J. Nussbaumer:「高速フーリエ変換のアルゴリズム」、科学技術出版社、ISBN 978-4876530069 (1989年).
William L. Briggs and Van Emden Henson: "The DFT: An Owners' Manual for the Discrete Fourier Transform", SIAM, ISBN 978-0-898713-42-8 (1995年).
Gerlind Plonka, Daniel Potts, Gabriele Steidl and Manfred Tasche: "Numerical Fourier Analysis", Birkhaeuser, ISBN 978-3030043056 (2019年2月).
谷萩隆嗣:「高速アルゴリズムと並列信号処理」、コロナ社、ISBN 4-339-01124-X(2000年7月26日)。
s = 0, 1, ..., P − 1 と r = 0, 1, ..., Q − 1 について F ( s Q + r ) = ∑ p = 0 P − 1 exp  ( − 2 π i s p P ) f 1 ( p , r ) {\displaystyle F(sQ+r)=\sum _{p=0}^{P-1}\exp \left(-2\pi i{\frac {sp}{P}}\right)f_{1}(p,r)}
を計算する。ここで、右辺は r を固定すれば、P 次の離散フーリエ変換である。
ステップ1、2は、N = PQ 次の離散フーリエ変換を、Q 次の離散フーリエ変換と回転因子の掛け算の実行により、Q 組 (r = 0, 1, ..., Q − 1) の P 次離散フーリエ変換に分解したと見ることができる。
N = Q (P = Q) の場合には、上を繰り返せば、Q 次の離散フーリエ変換と回転因子の掛け算を繰り返すことだけで次数を下げることができ、最終的に1次離散フーリエ変換(何もしないことと同じ)にまで下げると、F(t)を求めることができる。特に、Q が2または4の場合は、Q次の離散フーリエ変換は非常に簡単な計算になる。
このように、求める解 F ( r k Q k − 1 + ⋯ + r 2 Q + r 1 ) {\displaystyle F(r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1})} が f ( r 1 Q k − 1 + r 2 Q k − 2 + ⋯ + r k − 1 Q + r k ) {\displaystyle f(r_{1}Q^{k-1}+r_{2}Q^{k-2}+\cdots +r_{k-1}Q+r_{k})} のあった場所に格納されていることを、ビット反転と言う。これは、Q 進法で表示した場合、 r k Q k − 1 + ⋯ + r 2 Q + r 1 {\displaystyle r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1}} は ( r k r k − 1 ... r 2 r 1 ) Q {\displaystyle (r_{k}r_{k-1}\dots r_{2}r_{1})_{Q}} となるのに対し、 r 1 Q k − 1 + r 2 Q k − 2 + ⋯ + r k − 1 + r k {\displaystyle r_{1}Q^{k-1}+r_{2}Q^{k-2}+\cdots +r_{k-1}+r_{k}} は逆から読んだ ( r 1 r 2 ... r k − 1 r k ) Q {\displaystyle (r_{1}r_{2}\dots r_{k-1}r_{k})_{Q}} となるためである。
複素関数 f(x) の離散フーリエ変換である複素関数 F(t) は以下で定義される。
F ( t ) = ∑ x = 0 N − 1 f ( x ) exp  ( − i 2 π t x N ) . {\displaystyle F(t)=\sum _{x=0}^{N-1}f(x)\exp \left(-i{\frac {2\pi tx}{N}}\right).}
このとき、{x = 0, 1, 2, ..., N − 1} を標本点と言う。
これを直接計算したときの時間計算量は、ランダウの記号を用いて表現すると O(N) である。
高速フーリエ変換は、この結果を、次数Nが2の累乗のときに O(N log N) の計算量で得るアルゴリズムである。より一般的には、次数が N = ∏ ni と素因数分解できるとき、O(N∑ni) の計算量となる。次数が 2 の累乗のときが最も高速に計算でき、アルゴリズムも単純になるので、0 詰めで次数を調整することもある。
高速フーリエ変換を使って、畳み込み積分などの計算を高速に求めることができる。これも計算量を O(N) から O(N log N) まで落とせる。
現在は、初期の手法 をより高速化したアルゴリズムが使用されている。