高速フーリエ変換を使用した多項式乗算

StackOverflow https://stackoverflow.com/questions/1257010

  •  12-09-2019
  •  | 
  •  

質問

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}}
役に立ちましたか？

解決

多項式 A(x) と定義されている

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

FFT による多項式乗算の分割統治戦略を開始するために、CLRS は 2 つの新しい多項式を導入します。の偶数乗の係数の 1 つ x 呼ばれた A[0] の奇数乗の係数の 1 つ x 呼ばれた A[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)

Q.E.D.

他のヒント

多項式を「奇数の指数」と「偶数の指数」に分けると、A[1] 多項式 (奇数の指数を持つもの) の指数が奇数であるという厄介な事実がわかります。FFT では、指数さえも扱いやすくなります。したがって、A[1] のすべての値から単一の「x」を単純に因数分解し、それを式の外に移動することができます。

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

編集：あなたの混乱は、(x^2) を 価値 多項式で。A[1] および A[0] の「x」は、(x^2) 式の x とは異なります。元の多項式 A は指数 N まで上がりますが、A[1] と A[0] はどちらも指数 (N/2) までしか上がりません。

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

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

\sum_{i=0} ^n {xi y{n-i}}。

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

次に、次のことを考えてみましょう。

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{i-k}) 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 個の点を選択する必要があります。ここで、2^m が n 以上の 2 の最小累乗となるように m が選択されます。

A(x) is broken in to even x^2, and odd x parts,

for example if A(x) = 21 x^5 + 17 x^4 + 33 x^3 + 4 x^2 + 8 x + 7

then A0 = 17 y^2 + 4 y + 7
     so that A0(x^2) = 17 x^4 + 4 x^2 + 7

and  A1 = 21 y^2 + 33 y + 8
     so that A1(x^2) = 21 x^4 + 33 x^2 + 8
     or  x * A1(x^2) = 21 x^5 + 33 x^3 + 8 x

clearly, in this case, A(x) = A0(x^2) + x A1(x^2) = even + odd parts
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top