FFT

作者: ffacs 分类: 总结 发布时间: 2020-05-05 09:25

点值表示法

$n$个二维平面上的点$(x_1,y_1)…(x_n,y_n)$,确定了唯一一个过这些点的 $n-1$次多项式。

证明:设 $n-1$ 次多项式 $f(x),g(x)$ 都经过这 $n$ 个点,设 $n-1$ 次多项式 $y(x)=f(x)-g(x)$,那么$y(x_1)=y(x_2)=…y(x_n)=0$ ,即这个 $n-1$ 次多项式有 $n$ 个根。与代数基本定理相悖,所以只可能有一个 $n-1$ 次多项式过这 $n$ 个点。

复数中的单位根

将复平面上的单位圆等分成 $n$ 个部分(以单位圆与实轴正半轴的交点一个等分点),以原点为起点,圆的这 $n$ 个 $n$ 等分点为终点,作出 $n$个向量。其中幅角为正且最小的向量称为 $n$ 次单位向量,记作 $\omega_n^1$。根据欧拉幅角公式,
$$
\omega_n^k=e^{\frac{ik2\pi}{n}}
$$
又有$\omega_n^k=\omega_n^{k-1}*\omega_n^{1}$

单位根的性质

$\omega_n^k=\omega_n^{n+k}$ : 一个向量转了 $2\pi$ 以后等于自己

$\omega_n^k=-\omega_n^{k+n/2}$ :一个向量转了半圈以后等于原来自己的相反

$\omega_{2n}^{2k}=\omega_{n}^k$ : 分成$2n$ 份取 $2k$ 份等于 分成 $n$ 份 取 $k$ 份

离散傅里叶变换(Discrete Fourier Transform)

一个 $n=2^{k}$ 项($n-1$次)多项式 $A(x)$,其系数分别为$(a_0,a_1..a_{n-1})$,我们分别将 $n$ 次单位根的 $0\sim n-1$ 代入 $A(x)$ 得到 $A(\omega_{n}^{0}),A(\omega_{n}^{1})…A(\omega_{n}^{n-1})$。这个过程称为 离散傅里叶变换

快速离散傅里叶变换(Fast Fourier Transform)

如果朴素地代入的话那么复杂度是 $O(n^2)$ 的。我们考虑用单位根的性质来加速。

对于 $n-1=2^k-1$ 次多项式
$$
A(x)=a_{0}+a_1{x}+a_{2}x^{2}…+a_{n-1}x^{n-1}
$$
我们要求其在 $\omega_{n}^{0},\omega_{n}^{1}…\omega_{n}^{n}$ 的值

考虑对 $x$ 奇偶分组
$$
\begin{align}
A(x) &= (a_{0}+a_{2}x^{2}+a_{4}x^{4}…+a_{n-2}x^{n-2}) + (a_{1}x+a_{3}x^{3}+a_{5}x^{5}…+a_{n-1}x^{n-1}) \\
&= (a_{0}+a_{2}x^{2}+a_{4}x^{4}…+a_{n-2}x^{n-2}) + x(a_{1}+a_{3}x^{2}+a_{5}x^{4}…+a_{n-1}x^{n-2}) \\
\end{align}
$$
我们设
$$
A_1(x)=(a_0+a_2x+a_4x^{2}…+a_{n-2}x^{\frac{n-2}{2}}) \\
A_2(x)=(a_1+a_3x+a_5x^{2}…+a_{n-1}x^{\frac{n-2}{2}}) \\
$$
则有
$$
\begin{align}
A(x)&=A_1(x^2)+xA_2(x^2) \
A(\omega_n^k) &= A_1(\omega_n^{2k})+\omega_{n}^{k}A_2({\omega_n^{2k})} \\
\end{align}
$$
当 $k \le n/2-1$
$$
A(\omega_n^k) = A_1(\omega_{n/2}^{k})+\omega_{n}^{k}A_2(\omega_{n/2}^{k}) \\
$$
当 $n/2 \le k+n/2 \le n-1$
$$
\begin{align}
A(\omega_n^{k+n/2}) &= A_1(\omega_{n}^{2k+n})+\omega_{n}^{k+n/2}A_2(\omega_{n}^{2k+n}) \\
&= A_1(\omega_{n/2}^{k})-\omega_{n}^{k}A_2({\omega_{n/2}^{k})} \\
\end{align}
$$
那么我们只要知道 $A_1,A_2$ 在$\omega_{n/2}^{0}…\omega_{n/2}^{n/2-1}$ 的取值,我们就可以 $O(n)$ 地求出 $A$ 在 $\omega_{n}^{0}..\omega_{n}^{n-1}$ 的取值了。

这样总复杂度就是 $O(n\log n)$

反离散傅里叶变换(Inverse Discrete Fourier Transform)

与离散傅里叶变换相反,反离散傅里叶变换是知道多项式$A(x)$ 在 $\omega_{n}^{0},\omega_{n}^{1}…\omega_{n}^{n-1}$ 的值,需要求出 $A(x)$ 的系数。

定理: 设 $b_0,b_1,b_2…b_{n-1}$ 是 $A(x)$ 在 $\omega_{n}^{0},\omega_{n}^{1}…\omega_{n}^{n}$ 的取值, $c_0,c_1…c_n$ 是多项式 $b_0+b_1x+b_2x^2…b_{n-1}x^{n-1}$ 在 $\omega_{n}^{0},\omega_{n}^{-1}…\omega_{n}^{-(n-1)}$ 的取值,则 $a_i=c_i/n$

证明:

首先因为当 $j \neq 0$ 时有 $(\omega_n^{k})^0+(\omega_n^{k})^1+…(\omega_n^{k})^{n-1}=0$, (对称)

得到
$$
\begin{align}
a_k&=\frac{1}{n}\sum_\limits{j=0}^\limits{n-1}a_j(\sum_\limits{i=0}^\limits{n-1}(\omega_n^{j-k})^i \\
&=\frac{1}{n}\sum_{j=0}^{n-1}a_j\sum_{i=0}^{n-1}(\omega_n^{j})^i(\omega_n^{-k})^i \\
&=\frac{1}{n}\sum_\limits{j=0}^\limits{n-1}\sum_\limits{i=0}^\limits{n-1}(\omega_n^{i})^j(\omega_n^{-k})^ia_j \\
&=\frac{1}{n}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}(\omega_n^{i})^j(\omega_n^{-k})^ia_j \\
&=\frac{1}{n}\sum_{i=0}^{n-1}(\omega_n^{-k})^i\sum_{j=0}^{n-1}(\omega_n^{i})^ja_j \\
&=\frac{1}{n}\sum_{i=0}^{n-1}b_i(\omega_n^{-k})^i
\end{align}
$$

注意到 $\omega_n^{-k}$ 是$\omega_n^{k}$ 的共轭复数。所以对于$\text{IDFT}$,我们只要将多项式的系数换为在 $\omega_{n}^{0},\omega_{n}^{1}…\omega_{n}^{n-1}$ 的值,单位根变成共轭复数做$\texttt{DFT}$ ,再将得到的结果$/n$ 即可。

多项式乘法

给定 $n$ 次多项式 $A(x)$, $m$ 次多项式 $B(x)$ ,求 多项式 $C(x)=A(x) * B(x)$

如果朴素地将系数进行相乘那么复杂度是 $O(nm)$,既然 $C(x)=A(x)*B(x)$ ,那么 $C(x)$ 的次数就是 $n+m$,我们将它补齐到 $2^k$,接下来我们只要知道 $A(x)$ 和 $B(x)$ 的 $\text{DFT}$ 结果,再进行相乘,就得到了 $C(x)$ 的 $\text{DFT}$ 结果。再进行一次 $\text{IDFT}$ ,时间复杂度就降到了 $O(n \log n)$

2条评论
  • 包子

    五月 9, 2020 3:49 下午

    代码呢代码呢代码呢

    1. ffacs

      五月 9, 2020 6:14 下午

发表评论

电子邮件地址不会被公开。 必填项已用*标注