なぜ高速フーリエ変換はO(n*log n)で計算できるのでしょうか？ どうか理由を詳しく教えて下さい

なぜ高速フーリエ変換はO(n*log n)で計算できるのでしょうか？
どうか理由を詳しく教えて下さい。

質問者からの補足コメント

• わたしは 「X0 = f0･W^0 + f1･W^0 + f2･W^0 + f3･W^0
  X1 = f0･W^0 + f1･W^1 + f2･W^2 + f3･W^3
  X2 = f0･W^0 + f1･W^2 + f2･W^4 + f3･W^6
  X3 = f0･W^0 + f1･W^3 + f2･W^6 + f3･W^9
  となるがW^(km)の性質から
  X0 = f0･W^0 + f1･W^0 + f2･W^0 + f3･W^0
  X1 = f0･W^0 + f1･W^1 - f2･W^0 - f3･W^1
  X2 = f0･W^0 - f1･W^0 + f2･W^0 - f3･W^0
  X3 = f0･W^0 - f1･W^1 - f2･W^0 + f3･W^1
  と簡単になる。しかし、これでも16回の掛け算が必要なのは変わらない。そこで上の式を奇数行と偶数行に分けた。

    補足日時：2022/03/20 07:06

• X0 = f0･W^0 + f1･W^0 + f2･W^0 + f3･W^0
  X2 = f0･W^0 - f1･W^0 + f2･W^0 - f3･W^0
  X1 = f0･W^0 + f1･W^1 - f2･W^0 - f3･W^1
  X3 = f0･W^0 - f1･W^1 - f2･W^0 + f3･W^1
  ここからは上の展開式を行列で表さないとわかりにくいのだが、メンドーなので省略する。

    補足日時：2022/03/20 07:07

• とにかく上のように行を入れ替えると
  X0 = W^0(f0+f2) + W^0(f1+f3)
  X2 = W^0(f0+f2) - W^0(f1+f3)
  X1 = W^0(f0-f2) + W^1(f1-f3)
  X3 = W^0(f0-f2) - W^1(f1-f3)
  のように8個の掛け算だけで済むように変形できる。これがバタフライ演算である」と考えたため、バタフライ演算からO(n*log n)が導けたのではないかと考えました。

    補足日時：2022/03/20 07:07

• ちなみに、画像の青い下線部の二つの式を組み合わせると水色で書かれた高速フーリエ変換の式(2)になると思うのですが、それ以前に青い下線部の二つの式はなんなのですか？

  
    補足日時：2022/03/21 16:00

• 図はn=8の場合だけど、3段(=log[2]8)のバタフライ
  (3回の計算)で処理してる。と言われたのですが
  3段ではなく4段ではないでしょうか？

  
    補足日時：2022/03/24 18:48

• なるほど、nは処理前のデータの量で、nを8とした時のバタフライ演算の回数が4回だと解りました。

    補足日時：2022/03/25 12:17

• usa3usa様、
  
  編集致します。
  
  「nは処理前のデータの量で、nを8とした時のバタフライ演算の回数が4回」
  ではなく、正しくは
  「nは処理前のデータの量で、nを8とした時のバタフライ演算を適応した場合の掛け算の回数が4回」
  という事でしょうか？
  
  また、
  
  バタフライ演算を適応した場合の掛け算の回数は画像のどの部分を表しているのでしょうか？

  
    補足日時：2022/03/29 13:46

• 4回と出したのは画像より、赤で囲まれたバタフライ演算の回数が4回のバタフライ演算を行っているため4回と書きました。

  
    補足日時：2022/03/30 07:09

• なるほど、
  「
  　図から明らかなように、処理するデータ数が N = 8 の時より
  第1ステージ(1段目)の N = 8 のバタフライ演算は1組
  　1組の乗算回数は4回だから計1×4=4回
  第2ステージ(2段目)の N = 4 のバタフライ演算は2組
  　1組の乗算回数は2回だから計2×2=4回
  第3ステージ(3段目)の N = 2 のバタフライ演算が4組
  　1組の乗算回数は1回だから計4×1=4回
  　だから、バタフライ演算の乗算回数の合計は12回。」

  
    補足日時：2022/03/30 08:03

• この各段のバタフライ演算の乗算回数を素早く求めるためにO(Nlog(N))(N=8の時、乗算回数は8log(8)=12、すなわち乗算回数は12回)を作ったのですね。
  そのため、「バタフライ演算を適応した場合の掛け算の回数」が12回とわかりました。
  
  以前私が言っていた「バタフライ演算の回数が4回」とは画像より各段のバタフライ演算のそれぞれの乗算回数の計が4回を表しているのだとわかりました。
  
  合っていますでしょうか？

    補足日時：2022/03/30 08:03

No.1 回答者： tknakamuri 回答日時： 2022/03/19 21:31

一段のバタフライの演算量はnに比例

それを1ogn段やるのだから
nlogn
バタフライ演算の図を見れば一目瞭然です。

この回答へのお礼

ありがとうございます。
あの「一段のバタフライの演算量はnに比例」に関してnとは何を表しているのですか？
また、なぜ比例するのでしょうか？
出来れば比例する理由を簡単で良いのでバタフライ演算とO(n*log n)を用いて具体例を挙げていただけないでしょうか？

どうかよろしくお願い致します。

お礼日時：2022/03/20 07:01

No.2 回答者： usa3usa 回答日時： 2022/03/19 23:22

＞なぜ高速フーリエ変換はO(n*log n)で計算できるのでしょうか？

＞どうか理由を詳しく教えて下さい。
「計算回数を激減できるバタフライ演算で計算する」から
です
https://oshiete.goo.ne.jp/qa/12836998.html

（＊）「計算回数を激減できる」とはO(n²) を O(n*log n) にするという意味です。

この回答へのお礼

usa3usa様、解答ありがとうございます。
では、O(n*log n)を展開したものがバタフライ演算という事でしょうか？
だとしたら、簡単なバタフライ演算からO(n*log n)を導くまでを教えて頂けないでしょうか？

また、O(n*log n)のOは何を表しているのでしょうか？

どうかよろしくお願い致します。

お礼日時：2022/03/20 06:54

No.3 回答者： usa3usa 回答日時： 2022/03/20 06:48

No2です

手を変え品を変え、同じ質問を何度もされているような気がしています
説明を何度も求めるのではなく、自分で「説明を生み出す努力」をしたほうが、納得できる説明が得られる気がします。

＞どうか理由を詳しく教えて下さい。
→　私はｘｘと考えましたが、「O(n*log n)で計算できる」という結論にたどり着けません。
といった質問であれば、どこでつまずいているのか一緒になって悩んで差し上げますよ。

＜余談＞
NｘNの正方行列の行列式を、求める場合をバタフライ演算を使わずに計算する場合
次に1回バタフライ演算を使って計算する場合
2回バタフライ演算を使って計算する場合
：
1回バタフライ演算をするごとに、計算回数はどう変化するのか？
バタフライ演算は永遠に使うことができるのか？

これからは、少なくとも以上のことを自問自答してから、質問されたら良いと思います。

この回答へのお礼

ありがとうございます。
ちなみに、O(n*log n)のOは何を表しているのでしょうか？

お礼日時：2022/03/20 07:08

No.4 回答者： usa3usa 回答日時： 2022/03/20 12:03

＞ちなみに、O(n*log n)のOは何を表しているのでしょうか？

O記法（オーダー記法）のOです。計算にかかる時間とデータ量の関係について表した記法です。
https://note.com/strictlyes/n/n82d0a3874256

＞のように8個の掛け算だけで済むように変形できる。これがバタフライ演算である」と考えたため、バタフライ演算からO(n*log n)が導けたのではないかと考えました。

あってますよ。
16回の掛け算が必要、8個の掛け算だけで済むといった具体的な数値をNに置き換えて、作文すればよいだけでは？

No.5 回答者： tknakamuri 回答日時： 2022/03/21 01:46

自分で質問した内容さえ理解してないというのは

先が長いね。

>あの「一段のバタフライの演算量はnに比例」に
>関してnとは何を表しているのですか？

nは処理前のデータの量。FFTではサンプルデータ数。

図はn=8の場合だけど、3段(=log[2]8)のバタフライ
で処理してる。

各段でバタフライの矢印数が変わらない事を確かめよう。
バタフライの演算量は矢印の数に比例する。

DFTが倍のDFTに分解されて行くのも図から一目瞭然だ。

この回答へのお礼

解説ありがとうございます。
図まで載せて頂きありがとうございます。
ただ、少し理解できていないところがあるのですが、n=8の時に演算量は4回になるのに、なぜ矢印数の数は変わらないのでしょうか？

また、最後にn回のバタフライ演算の計算式からO(n*log n)の公式を導くまでの計算過程を教えて頂けないでしょうか？

お礼日時：2022/03/21 05:46

No.6 回答者： usa3usa 回答日時： 2022/03/21 07:42

>最後にn回のバタフライ演算の計算式からO(n*log n)の公式を導くまでの計算過程を教えて頂けないでしょうか？

だ・・か・・ら・・
説明を何度も求めるのではなく、自分で「説明を生み出す努力」をしましょう
N＝８の場合を参考に、実際の高速フーリエ変換が使われる場合のNとして、例えば

N=２５６の場合
N=５１２の場合
N=１０２４の場合
を想定し、自分の頭をつかって、手を動かして紙に書いてやってみましょう。
この一連の作業を通して、
計算回数を激減できることを「体感」し、
激減の度合いを「定式化したいと感じ」てから、
O(n*log n)の公式を「導いて」みましょう。

No.7 回答者： tknakamuri 回答日時： 2022/03/21 19:49

>n=8の時に演算量は4回になるのに、

>なぜ矢印数の数は変わらないのでしょうか？

図を見れば一目瞭然だけど
名段でデ―タ数はずうっと8
各段でバタフライ数はずうっと4組

バタフライは2入力、2出力なんだから
当たり前。

この回答へのお礼

ありがとうございます。
今更で申し訳ないのですが、
>> 「図を見れば一目瞭然だけど
名段でデ―タ数はずうっと8
各段でバタフライ数はずうっと4組

バタフライは2入力、2出力なんだから
当たり前。」
に関して、なぜ入力と出力の数値が同じなのに、n=8の時に演算量が4と異なるのでしょうか？

どうかよろしくお願い致します。

お礼日時：2022/03/23 19:01

No.8 回答者： usa3usa 回答日時： 2022/03/22 08:15

>ちなみに、画像の青い下線部の二つの式を組み合わせると水色で書かれた高速フーリエ変換の式(2)になると思うのですが、それ以前に青い下線部の二つの式はなんなのですか？

新な疑問は、別の質問とすることかな

脇道にそれずに、下記のA-Jを埋めれば、本件の質問の答えになるので、自分で「説明を生み出す努力」をしましょう
ーーーーーーーーーー
N＝８の場合は、普通に計算すると＿A＿回の掛け算が必要だが、バタフライ演算を適応すると＿B＿回の掛け算で計算できる。

N＝２５６の場合は、普通に計算すると＿C＿回の掛け算が必要だが、バタフライ演算を適応すると＿D＿回の掛け算で計算できる。

N＝５１２の場合は、普通に計算すると＿E＿回の掛け算が必要だが、バタフライ演算を適応すると＿F＿回の掛け算で計算できる。

N＝１０２４の場合は、普通に計算すると＿G＿回の掛け算が必要だが、バタフライ演算を適応すると＿H＿回の掛け算で計算できる。

以上のことから、一般にN＝２＾Kの場合は、普通に計算すると＿I＿回の掛け算が必要だが、バタフライ演算を適応すると＿J＿回の掛け算で計算できる。

すなわち、バタフライ演算を用いないとO(n＾２)であるが、バタフライ演算を用いる高速フーリエ変換はO(n*log n)で計算できる。

この回答へのお礼

ちなみに、nは処理前のデータの量として、nを8とした時の「バタフライ演算の回数」も「バタフライ演算を適応した場合の掛け算の回数」も4回なのでしょうか？

どうかよろしくお願いします。

お礼日時：2022/03/29 14:52

No.9 回答者： tknakamuri 回答日時： 2022/03/24 05:32

>n=8の時に演算量が4と異なるのでしょうか？

全然言葉が通じないね。
意思疎通不可能みたいなので私は撤退します。

この回答へのお礼

理解できなくて申し訳ない。

お礼日時：2022/03/24 18:48

No.10 回答者： usa3usa 回答日時： 2022/03/25 17:31

No8 です

>なるほど、nは処理前のデータの量で、nを8とした時のバタフライ演算の回数が4回だと解りました。

本件の質問の解決のために着目するのは、
　バタフライ演算の回数
でなく
　バタフライ演算を適応した場合の掛け算の回数
ですよ。

この回答へのお礼

ありがとうございます。
だとしたら、「nは処理前のデータの量で、nを8とした時のバタフライ演算の回数が4回」
ではなく、「nは処理前のデータの量で、nを8とした時のバタフライ演算を適応した場合の掛け算の回数が4回」という事でしょうか？

お礼日時：2022/03/29 13:23