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 引入了两个新多项式：被调用的偶次幂系数和被调用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]and 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)and 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)

量子点

于 2009-08-10T20:48:58.763 回答
3

如果您将多项式划分为“奇数指数”和“偶数指数”，您会发现 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)。

于 2009-08-10T20:47:47.237 回答
1

我不会回答你的问题，因为我觉得以前的人已经回答过了。我要做的是尝试解释 FFT 的目的。

首先，FFT 是一种计算两个向量之间卷积的方法。也就是说，假设 x = 和 y= 是 1xn 个向量，那么 x 和 y 的卷积是

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

您将不得不接受这样一个事实，即计算该值在广泛的应用程序中非常有用。

现在考虑以下内容。

假设我们构造两个多项式

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 值的不同大小的卷积。

Now we can clearly compute the coefficients (convolutions) of AB in n^2 time by a brute force method.

However, we can also be much more clever. Consider the fact that any polynomial of degree n can be described uniquely by n+1 points. That is given n+1 points we can construct the unique polynomial of degree n that goes through all n+1 points. Further more consider 2 polynomials in the form of n+1 points. You can compute their product by simply multiplying the n+1 y-values and keeping the x-values to result in their product in point-form. Now given a polynomial in n+1 point-form you can find the unique polynomial that describes it in O(n) time (actually Im not sure about this, it may be O(nlogn) time but certainly not more.)

This is exactly what the FFT does. However, the points that it picks to get the n+1 points to described the polynomials A and B are VERY carefully chosen. Some of the points are indeed complex because it just so happens that you can save time in evaluating a Polynomial by considering such points. That is if you were to choose just real points instead of the carefully chosen points that the FFT uses you would need O(n^2) time to evaluate the n+1 points. If you choose the FFT you only need O(nlogn) time. And thats all there is to the FFT. Oh and there is a unique side effect to the way that the FFT chooses points. Given an n-th degree polynomial, you must choose 2^m points where m is chosen such that 2^m is the smallest power of 2 greater than or equal to n.

于 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 回答