FFT变换-学习笔记

1.多项式相乘

怎么来表示两个多项式相乘呢？

（1）在线性代数里面我们是可以用多项式的系数来表示一个多项式，两个多项式的相乘也就是两个多项式的系数分别乘上彼此的系数（交叉相乘求和），最终得到的就是两个多项式相乘的系数所表示的多项式，这样可以确定唯一的多项式。

（2）还有一种表示方法就是用点来确定，叫做值表示法，比如我们所知的两个点确定一条一阶直线，三个点可确定一条二阶曲线，那么推广开来：d+1个点就可以确定d阶的曲线，这样也是唯一确定的。

所以在计算两个多项式相乘结果的时候我们可以采用（1）中的系数相乘法，这样结果的计算复杂度为o（
$n^{2}$
）,而采用（2）用n+1个点来确定的话那么只需要在两个多项式里面分别取n+1个点然后对应相乘，此时只相乘了n+1次就可得到n+1个点，从而确定两个多项式相乘结果的多项式，并且计算的复杂度为o(n)。

所以现在我们的思路就是通过两个多项式A、B的系数，然后从两个多项式中取点，求出点的值，然后根据求出来的值和取的点反推回C的系数，就这样多项式相乘的结果就出来了。那么在求值的过程中就是FFT要做的事情（卷积过程），在反推系数的过程中就是IFFT做的事情（卷积逆运算）。

那么是不是在计算C(x)=A(x)*B(x)时，就从A(x)和B(x)取n+1个x带入到A(x)与B(x)中然后求出n+1个点相乘？

当然不是这么简单的去取点，如果这样做的话最终复杂度还是o(
$n^{2}$
)，因为每个点的计算复杂度都是o(n)，然后又有n个点，最终复杂度还是 o(
$n^{2}$
)。

2.怎么取点

如果要计算n个点的值，我们是否需要取n个点，然后求n次值呢，当然是不需要的，从下图可以看出，当点具有奇偶性时我们就只需要取一半的点就可以得到所有的值。

所以根据以上的理论基础我们可以先将一个多项式的奇数项写一起，偶数项写一起：

$A(x)=a_{0}+a_{1}x+...+a_{n-1}x^{n-1} =a_{0}+a_{2}x^{2}+...+a_{n-2}x^{n-2}+a_{1}x+a_{3}x^{3}+...+a_{n-1}x^{n-1}$

$A_{1}(x)=a_{0}+a_{2}x+...+a_{n-2}x^{n/2-1}$

$A_{2}(x)=a_{1}x+a_{3}x^{2}...+a_{n-1}x^{n/2-1}$

所以：

$A(x)=A_{1}(x^{2})+xA_{2}(x^{2})$

$A(-x)=A_{1}(x^{2})-xA_{2}(x^{2})$

如果我们有n-1阶多项式需要取n个点，那么根据奇偶性我们只需要取n/2-1个点，而每部分都是n/2-1阶。现在变成求 n/2-1个点的n/2-1 阶的多项式的值，那么我们又怎么求这 n/2-1 阶的多项式的值呢，当然还是用同样的方法，再把关于x^2的多项式根据奇偶拆分，一直拆分………，一直分到最后只求1个点的值，因为一个点的值比较好算，所以我们得到一个点的值再反推回去，那么就可以得到n个点开n次方的值，就可以得到这个多项式的n个点所有值了。

到这里之后就很像是递归的算法了，但是目前还有一个问题就是第一次分奇偶自变量可以取±x得出来A(x),A(-x),然而在第二次分的时候原式子中全是x^2的多项式怎么能将自变量取成一正一负的形式呢，所以为了使得递归成立，FFT引入了复数，如果令x1=1的话：

可见有了复数的加入递归算法就成立了，那么整个计算的复杂度为o(nlogn)，因为一直在做对半分的操作，所以在取FFT的点数的时候尽量取2^n个，对于不够的则补零。也可以看出我们所需要取的点就是1开n次方后的n个值，我们要求这n个值是n/2对相反数。

3.单位根

由上文我们知道需要取的点就是1开n次方后呈互为相反数的n个点，所以FFT又引入了单位圆复平面，因为1的n次方根可以解释为复平面上沿着单位圆等距排布的一系列点。

设幅角为正且最小的复数为
$\omega _{n}$
,这就是n次单位根，表达式为（由欧拉公式推）：

$\omega _{n}=cos\frac{2\pi }{n}+isin\frac{2\pi }{n}$

而所有的单位根的表达式为：

$\omega _{n}^{k}=cos\frac{2k\pi }{n}+isin\frac{2k\pi }{n}$

单位根有一些性质：

（1）折半引理

$\omega _{n}^{2k}=\omega _{n}^{k}$

$\omega _{n}^{k+\frac{n}{2}}=-\omega _{n}^{k}$

（2）

$\omega _{n}^{0}=\omega _{n}^{n}$

（3）加法引理

$\omega _{n}^{i}*\omega _{n}^{j}=\omega _{n}^{i+j}$

（4）消去引理

$\omega _{dn}^{dk}=\omega _{n}^{k}$

由上式（1）可见在单位圆上所有的点的取值都有存在其相反数，点平方后还是和原复数相等，当单位圆上的点平方后点数减半，但依旧满足所有点存在相反数。

4.FFT实现

以上的单位根的性质正好满足咱们所需要的点的要求，所以将所取的点换成
$\omega _{n}^{k}$
。

那么此时第一部分多项式：

$A(\omega _{n}^{k})=A_{1}(\omega _{n}^{2k})+\omega _{n}^{k}A_{2}(\omega _{n}^{2k})$

折半引理后：

$A(\omega _{n}^{k})=A_{1}(\omega _{\frac{n}{2}}^{k})+\omega _{n}^{k}A_{2}(\omega _{\frac{n}{2}}^{k}) , k\epsilon [0,\frac{n}{2}-1]$

第二部分多项式：

$A(\omega _{n}^{k+\frac{n}{2}})=A_{1}(\omega _{n}^{k+\frac{n}{2}})+\omega _{n}^{k+\frac{n}{2}}A_{2}(\omega _{n}^{k+\frac{n}{2}})$

折半引理后：

$A(\omega _{n}^{k})=A_{1}(\omega _{\frac{n}{2}}^{k})-\omega _{n}^{k}A_{2}(\omega _{\frac{n}{2}}^{k}) , k\epsilon [\frac{n}{2},n-1]$

最后不断递归就可以求出最终的值了，这个过程也就是FFT变换。

5.IFFT变换

FFT变换就是快速的DFT变换，DFT变换时是由一个多项式系数矩阵乘以DFT变换矩阵得到的一堆多项式值的矩阵。FFT则是当
$x_{k}=\omega^{k}$
(
$\omega =e^{\frac{2\pi i}{n}}$
)时的变换。

而IFFT则是跟FFT一样的原理，此时我们需要根据给出的多项式值求出多项式系数，将DFT变换矩阵求逆，然后乘上值向量最终得到多项式系数矩阵。而且在对DFT矩阵求逆后矩阵里的
$x_{k}=\omega^{-k}$
（
$\omega =\frac{1}{n}e^{\frac{-2\pi i}{n}}$
）,那么我们就可以使用FFT同样的方式来进行IFFT变换了。

以上分享均是自己在学习时的笔记，相关视频链接发出来被和谐，自行上某站搜索FFT 。

如有侵权，请联系我删除哈~~~~

原文链接：https://blog.csdn.net/qq_42640275/article/details/124003512

你可能也喜欢