1

多項式を評価しようとしているとしましょう:

x^2 + 1

係数の評価には高速フーリエ変換法を使用します。これで、係数を高速フーリエ変換の入力として使用して、これを行列/ベクトル形式に変更できます。

それで：

x^2 + 1 = <1, 0, 1, 0>

これは、1 = 1、0x^1 = 0、X^2 = 1 などの係数値を使用して行われます。

今、私は完全に混乱しています。Vandermonde matrix : Vandermonde matrix ~ Wikiを使用して、これらの値を次のマトリックスを使用して FFT 形式に評価することを意図しています。

1 1 1 1  
1 i-1-i
1-1 1-i
1-i 1 i

の出力

fft(1,0,1,0)

は

(2,0,2,0)

これは私がよく理解していないステップです。どのようにその行列を使用して (2,0,2,0) を取得したのでしょうか?

4

2 に答える 2

3

まず、ファンデルモンド行列が正しくありません。4番目の行は（-i） 0、（-i）1、（-i）2、（-i）3である必要があるため、（4,3）エントリは1ではなく-1である必要があります。特に注意してください

（-i）*（-i）=（-1）2 * i 2 = i 2 =-1。

この修正により、ファンデルモンド行列に列ベクトル（1,0,1,0）を乗算した結果が得られます。

于 2009-04-24T14:13:08.373 に答える
2

多分あなたはあなたの全体的な目標がここにあることを説明することができます。多項式の評価にFFTが使用されていることは聞いたことがありません。これらは、多項式の乗算、または信号の畳み込み（同等のタスク）に使用されますが、多項式/信号に多数の項がない限り、気にしません。x 2 +1は大きくありません。16項は大きくはなく、64または256項でさえ、単純なO（N 2）手法を使用した方がおそらく適切です。

離散フーリエ変換は、行列M ij = ωijを使用します。ここで、ωは1のN番目の複素数根であり、列/行の番号付けは0からN-1になります。

高速フーリエ変換は、この行列を直接使用することはありません。分割統治法（Cooley-Tukeyアルゴリズム）を使用して、直列および並列の2x2DFTのステージを通じて最終結果を計算するように高度に最適化されています。

ベクトルを[1,0,1,0]ではなく[0,1,0,1]と書くと、与えた行列を掛けると[0、 2,0,2]。（エラーがありますが、

1 1 1 1  
1 i-1-i
1-1 1-1
1-i-1 i

）使用しているプログラムには、ベクトルの係数の順序を逆にする規則が必要です。

于 2009-04-24T14:14:11.240 に答える