0

CLRS(CORMEN) (ページ 834 ) から上記のトピックを調べていますが、この時点で行き詰まりました。

どなたか、次の式の意味を説明していただけませんか?

A(x)=A^{[0]}(x^2) +xA^{[1]}(x^2)

から続く、

n-1                       `
 Σ  a_j x^j
j=0

どこ、

A^{[0]} = a_0 + a_2x + a_4a^x ... a_{n-2}x^{\frac{n}{2-1}}  
A^{[1]} = a_1 + a_3x + a_5a^x ... a_{n-1}x^{\frac{n}{2-1}}
4

4 に答える 4

4

多項式A(x)は次のように定義されます。

A(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ...

FFT による多項式乗算の分割統治戦略を開始するために、CLRS は 2 つの新しい多項式を導入しxます。A[0]xA[1]

A[0](x) = a_0 + a_2 x + a_4 x^2 + ...
A[1](x) = a_1 + a_3 x + a_5 x^2 + ...

とに代入x^2するA[0]とA[1]、次のようになります。

A[0](x^2) = a_0 + a_2 x^2 + a_4 x^4 + ...
A[1](x^2) = a_1 + a_3 x^2 + a_5 x^4 + ...

を掛けるA[1](x^2)とx、

x A[1](x^2) = a_1 x + a_3 x^3 + a_5 x^5 + ...

とを足すA[0](x^2)とx A[1](x^2)、

A[0](x^2) + x A[1](x^2) = (a_0 + a_2 x^2 + a_4 x^4 + ...) + (a_1 x + a_3 x^3 + a_5 x^5 + ...)
                        = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ...
                        = A(x)

QED

于 2009-08-10T20:48:58.763 に答える
3

多項式を「奇数指数」と「偶数指数」に分割すると、A[1] 多項式 (奇数指数を持つもの) が奇数指数を持っているという厄介な事実に気付くでしょう! FFTの場合、指数でさえ扱いやすくなります。したがって、A[1] のすべての値から 1 つの "x" を単純に除外し、それを式の外に移動できます。

FFT は、偶数指数多項式のみを扱うのが好きです。したがって、分割統治を行っている場合は、A[1] 式を「偶数指数」の多項式に変換し、その上で再帰してから、その xを乗算して戻す必要があります。実際のアルゴリズムの内側のループで発生することがわかります。

編集:あなたの混乱は、多項式の値として (x^2) を「渡している」という事実に起因する可能性があることを認識しています。A[1] と A[0] の "x" は、(x^2) 式の x とは異なります。元の多項式 A は指数 N まで上がりますが、A[1] と A[0] はどちらも指数 (N/2) までしか上がりません。

于 2009-08-10T20:47:47.237 に答える
1

前の人が答えたと思うので、あなたの質問には答えません。私がやろうとしていることは、FFT の目的を説明しようとすることです。

まず、FFT は 2 つのベクトル間の畳み込みを計算する方法です。つまり、x = と y= が 1xn ベクトルであるとすると、x と y の畳み込みは次のようになります。

\sum_{i=0} ^n {xi y{ni}}.

その値を計算することは、幅広いアプリケーションで非常に役立つという事実を受け入れる必要があります。

次に、次のことを検討してください。

2 つの多項式を構成するとします。

A(z) = x0 + x1*z + x2 *z^2 + .. + xn^z^n B(z) = y0 + y1*z + y2 *z^2 + .. + yn^z^n

次に、乗算は

AB(z) = A(z)B(z) = \sum_{i=0} ^ n (\sum_{k=0} ^ i xk*y{ik}) z^i

ここで、内側の合計は明らかに、k の値が異なる場合のサイズが異なる畳み込みです。

これで、強引な方法で n^2 時間で AB の係数 (畳み込み) を明確に計算できます。

しかし、私たちはもっと賢くなることもできます。次数 n の任意の多項式は、n+1 点で一意に記述できるという事実を考慮してください。n+1 個の点が与えられると、すべての n+1 個の点を通過する次数 n の一意の多項式を構築できます。さらに、n+1 点の形式で 2 つの多項式を考えます。n+1 の y 値を乗算し、x 値を保持して積を点形式にするだけで積を計算できます。n+1 点形式の多項式が与えられると、それを O(n) 時間で記述する一意の多項式を見つけることができます (実際には、これについてはよくわかりません。O(nlogn) 時間かもしれませんが、それ以上ではないことは確かです。)

これはまさにFFTが行うことです。ただし、多項式 A と B を表す n+1 点を取得するために選択する点は、非常に慎重に選択されています。いくつかの点は確かに複雑です。なぜなら、そのような点を考慮することで多項式を評価する時間を節約できるからです。つまり、FFT が使用する慎重に選択されたポイントの代わりに実際のポイントのみを選択した場合、n+1 ポイントを評価するのに O(n^2) 時間が必要になります。FFT を選択した場合、必要なのは O(nlogn) 時間だけです。FFTについては以上です。ああ、FFT がポイントを選択する方法には、独特の副作用があります。n 次の多項式が与えられた場合、2^m が n 以上の最小の 2 のべき乗になるように m が選択される 2^m 点を選択する必要があります。

于 2009-08-15T19:06:35.850 に答える
0 
A(x) は x^2 の偶数部分と x の奇数部分に分割され、

たとえば、A(x) = 21 x^5 + 17 x^4 + 33 x^3 + 4 x^2 + 8 x + 7 の場合

A0 = 17 y^2 + 4 y + 7
     A0(x^2) = 17 x^4 + 4 x^2 + 7 となるように

および A1 = 21 y^2 + 33 y + 8
     A1(x^2) = 21 x^4 + 33 x^2 + 8 となるように
     または x * A1(x^2) = 21 x^5 + 33 x^3 + 8 x

明らかに、この場合、 A(x) = A0(x^2) + x A1(x^2) = 偶数 + 奇数部分
于 2009-08-10T21:13:13.987 に答える