ＦＦＴでの計算コストの削減の理由が？

質問

ＤＦＴを半分に分割していくのがＦＦＴの特徴だと考えています。

で、どうしてＤＦＴを半分に分割していくと計算コストが下がるのかりかいできていません。
理由を教えていただけないでしょうか？

よろしくお願いいたします。

回答No.4

Tacosan · ベストアンサー

どこまで理解できているのかわからないのでちょっと不安だけど, まあだいたいそう思っていいです.

「データ数を半分にする」ごとに
・DFT に必要な時間が半分になる.
・回転因子を掛けるための時間 (これはデータ数に比例する) がかかる.

前者は計算時間を減らし, それに対し後者は計算時間を増やします. その結果「ある程度のところ」で両方に必要な時間がバランスし, そのとき計算時間は最短になります.

お礼

ご丁寧にありがとうぎざいました。まだわからない部分もありますが、自分で考えてみます。

回答No.3

noname#221368

計算量の評価は、#1さんの仰るとおりと思いますが、自分もFFTの原理は良くわかっていませんが、Nが大きくなると、FFTの方が無茶苦茶に速くなります（体感できます）。

　FFTの効率の良さは、三角関数の周期性を利用するところにあるみたいです。つまり変換区間のある値から周期分ずれた所では、sin，cosは同じ値を出すはずだ、という発想です。これを考慮しないDFTは、同じ値を何回も計算し、大量の無駄を行ってる事になります。

　周期性をうまく利用できるように、変換区間を半分づつに分割するのが、ミソみたいです。ｍを2以上の整数として、ｍ^nに分割してもFFTはできるそうです。効率は理屈ではいっしょです。

お礼

自分もＦＦＴの速さはさきほどプログラムを使って体感しました。ただ、どんな手法を経て計算コストが下がっているのか理解し切れてません。
アドバイスなどあれば教えてください。

回答No.2

Tacosan

そこは実は 4 に意味があるわけじゃないんだけどね.

Wikipedia の「高速フーリエ変換」の「原理の説明」を参考にするけど, N = PQ 個のデータに対する DFT は
1. Q 個のデータに対する DFT を P 回
2. 回転因子の乗算を合計 PQ 回
3. P 個のデータに対する DFT を Q 回
でできます. ここで, 「より少ない数のデータに対する DFT」だけではダメで, どうしても 2 の「回転因子の乗算」というステップが必要です. ここは PQ = N に比例する計算コストがかかります.

ということで, #1 の「+4N」はその分だと思ってください.

お礼

だんだんわかってきました。ありがとうございます。

つまり、２の回転因子の乗算のステップが必要ということは常に+4Nが発生するのでしょうか？

回答No.1

Tacosan

端的にいうと
N = 1024 のとき N^2 と 2×(N/2)^2 + 4N のどっちが大きいですか
ってことだ.

お礼

なるほど。よくわかりました。

ただ、最後の項の+4Nはどこからでてきたのですか？