algorithm - 使用快速傅立叶变换的多项式乘法

Question

我正在研究 CLRS(CORMEN) ( page 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}}

Answer 1

多项式A(x)定义为

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

为了启动 FFT 多项式乘法的分而治之策略，CLRS 引入了两个新多项式:x 的偶次幂系数之一称为 A[0 ] 和 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.