multiplication polynomiale en utilisant transformée de Fourier rapide

Question

Je vais à travers le sujet ci-dessus de CLRS (Cormen) ( Page 834 ) et je suis resté bloqué à ce stade.

Quelqu'un peut-il s'il vous plaît expliquer comment l'expression suivante,

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

suivante à partir,

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

Où,

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}}

Answer 1

est défini comme le A(x) polynôme

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

Pour commencer la stratégie de diviser pour mieux régner la multiplication polynomiale par la FFT, CLRS présente deux nouveaux polynômes: l'un des coefficients des même puissances de x appelé A[0] et l'un des coefficients des impairs puissances de x appelé 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 + ...

Maintenant, si nous remplaçons x^2 dans A[0] et A[1], nous avons

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 + ...

et si l'on multiplie par A[1](x^2) x, nous avons

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

Maintenant, si l'on ajoute A[0](x^2) et x A[1](x^2), nous avons

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.

Answer 2

Si vous divisons le polynôme jusqu'à en « exposants impairs » et « même exposants », vous trouverez le fait ennuyeux que le A [1] polynôme (celui avec des exposants impairs) a, exposants et impairs! Même les exposants sont plus faciles à travailler avec, pour FFT. Ainsi, on peut simplement factoriser un « x » de toutes les valeurs A [1], et le déplacer en dehors de l'expression.

FFT aime travailler avec seulement polynômes-même exponented. Ainsi, lorsque vous divisant et conquérante, vous voulez transformer votre A [1] expression dans un polynôme « même-exponented », et récursif à ce sujet, et puis se multiplient-retour en que x. Vous verrez qui se produisent dans la boucle interne de l'algorithme réel.

Edit: Je me rends compte que votre confusion peut provenir du fait qu'ils « en passant » (x ^ 2) comme valeur dans le polynôme. Le "x" dans A [1] et A [0] sont différents de X dans l'expression (x ^ 2). Vous verrez à quel point cela doit être, comme tout le polynôme d'origine A va jusqu'à l'exposant n, A [1] et A [0] aussi bien que aller jusqu'à exposant (N / 2).

Answer 3

Je ne vais pas répondre à votre question parce que je pense que les gens précédents ont répondu. Ce que je vais faire est d'essayer d'expliquer le but de la FFT.

Tout d'abord, la FFT est un moyen de calculer la convolution entre deux vecteurs. Cela est, supposons que x = et y = sont des vecteurs 1xN alors la convolution de x et y est

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

Vous devrez accepter le fait que le calcul de cette valeur est extrêmement utile dans un large éventail d'applications.

Considérons maintenant ce qui suit.

Supposons que nous construisons deux polynômes

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

alors la multiplication est

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

où la somme est à l'intérieur clairement une convolution de taille différente pour différentes valeurs de k.

Maintenant, nous pouvons calculer clairement les coefficients (circonvolutions) de AB n ^ 2 fois par une méthode de la force brute.

Cependant, nous pouvons être beaucoup plus intelligent. Tenir compte du fait que tout polynôme de degré n peut être décrite de façon unique par n + 1 points. Qui est donné n + 1 points, nous pouvons construire le unique polynôme de degré n qui passe par tous les n + 1 points. De plus envisager 2 polynômes sous la forme de n + 1 points. Vous pouvez calculer leur produit en multipliant simplement les n + 1 y valeurs et de garder les valeurs x pour entraîner leur produit au point de forme. Maintenant, étant donné un polynôme en n + 1 point formulaire, vous pouvez trouver le polynôme unique qui décrit en O (n) (en fait je ne suis pas sûr à ce sujet, il peut être O (nlogn) du temps, mais certainement pas plus.)

Ceci est exactement ce que fait la FFT. Cependant, les points qu'il cueille pour obtenir les n + 1 points pour décrire les polynômes A et B sont très soigneusement choisis. Certains des points sont en effet complexes, car il se trouve que vous pouvez gagner du temps dans l'évaluation d'un polynomiale en tenant compte de ces points. C'est si vous deviez choisir des points juste réel au lieu des points soigneusement choisis afin que la FFT vous auriez besoin utilise O (n ^ 2) le temps d'évaluer les n + 1 points. Si vous choisissez la FFT il vous suffit O (nlogn) temps. Et c'est tout ce qu'il ya à la FFT. Oh, et il y a un effet secondaire unique de la façon dont la FFT choisit des points. Étant donné un polynôme de degré n-ième, vous devez choisir 2 ^ m points où m est choisi de telle sorte que 2 ^ m est la plus petite puissance de 2 supérieure ou égale à n.

Answer 4

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