基于快速傅立叶变换的多项式乘法

多项式 A(x) 定义为

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

为了利用快速傅立叶变换启动多项式乘法的分而治之策略,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.

如果将多项式分为“奇数指数”和“偶数指数”,您会发现A[1]多项式(具有奇数指数的)具有令人讨厌的事实,即奇数指数!对于FFT,指数也更容易处理。因此,可以简单地从[1]中的所有值中分解出一个“x”,并将其移出表达式。

FFT只喜欢使用指数多项式。因此,当你划分和征服的时候,你想把你的一个[1]表达式变成一个“偶数指数”多项式,并在此基础上递归,和 然后 再乘以x,你会看到它出现在实际算法的内环中。

编辑:我意识到你的困惑可能源于他们“传递”(x^2)作为 价值 在多项式中。[1]和[0]中的“x”与(x^2)表达式中的x不同。你会看到它是怎样的,因为当原始多项式a上升到指数n时,a[1]和a[0]都只上升到指数(n/2)。

我不会回答你的问题,因为我觉得以前的人已经回答了。我要做的是解释快速傅立叶变换的目的。

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

[SUMi{{i=0 }^ ^ n {Xi-y{ni-i}}。

您必须接受这样一个事实,即计算该值在广泛的应用程序中非常有用。

现在考虑下面的内容。

假设我们构造两个多项式

a(z)=x0+x1*z+x2*z^2+…+xn^ z ^ n b(z)=y0+y1*z+y2*z^2+…+yn^ z ^ n

那么乘法就是

a b(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次多项式,它经过所有n+1点。进一步考虑2个n+1点形式的多项式。您可以通过简单地将n+1y值相乘并保持x值以得到点形式的乘积来计算它们的积。现在,给定一个n+1点形式的多项式,你可以找到用o(n)时间描述它的唯一多项式(实际上我不确定,它可能是o(nlogn)时间,但肯定不是更多)。

这正是FFT所做的。然而,它选择的点得到n+1点来描述多项式a和b是非常仔细的选择。有些点确实很复杂,因为它恰好如此,通过考虑这些点,可以节省计算多项式的时间。也就是说,如果只选择实数点而不是FFT使用的精心选择的点,则需要O(n^2)时间来评估n+1点。如果你选择快速飞行,你只需要O(非飞行)时间。这就是FFT的全部内容。哦,还有一个独特的副作用的方式,FFT选择点。给定一个n次多项式,你必须选择2^m点,其中m的选择使得2^m是大于或等于n的2的最小幂。

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)=偶数+奇数