DFT FFT NTT 是什么 & 为什么?

Posted on By 二价氢

最近在各种比赛中做了一些关于FFT的题目,感觉对FFT的理解还不是特别深刻,于是在网上搜了一些资料,整理出了关于DFT(FFT)和NTT的一些内容。

DFT

我们都知道,当我们用到FFT或者NTT的时候,都是各种多项式乘法的内容,于是问题来了,为什么它是对的?

先从线代的内容开始

考虑这样一个矩阵:

和这样一个向量 $x = \left(x_0, x_1, \cdots, x_{n-1}\right)^T$

如果它是线性无关的,且是可逆的,那么我们就有$AxA^{-1} = x$,我们发现这是一句废话,所以并没有多少实用价值。但是我们这时候就把$A$这个矩阵叫做变换好了。

我们知道,DFT的目的是为了做向量的卷积,即求出 $z = x \star y$ , 这里 $\star$ 表示卷积。

如何利用上面这些东西?

注意到 $z_v = \sum_{q} x_q y_{v-q}$

我们又注意到 $(Ax)_{u} =\sum_qx_qa_{u,q}$ 和 $(Ay)_{u} = \sum_q y_q a_{u,q}$

$(Ax)_{u} (Ay)_{u} = \sum_p\sum_q x_p y_q a_{u,p} a_{u,q}$

那么这个时候,如果我们在$z$边上加个求和符号的话,就得到了

那么如果再在左边加上一个 $a_{u,v}$ 呢?

啊,如果对于矩阵$A$,我们有 $a_{u,p}a_{u,q} = a_{u,p+q}$ 的话就好了,因为这样我们就可以得到一个重要的式子——

$Az = Ax \cdot Ay$

证明

由前文得到的

我们有

于是呢?

根据指数函数的性质,我们可以轻易构造出一组$A_{u,v} = b_u^v$异或

构造

当$b_u$两两不同的时候,$A$是可逆的。

性质

从上面这些内容,我们可以得出这个变换的一些性质:

  1. $Ax + Ay = A(x + y)$
  2. $A(kx) = kAx$
  3. $x\star y\star z = Ax \cdot Ay \cdot Az$ 推广得到 ${\Large\star} x_i = {\Large\cdot}Ax_i$
  4. $(x_1 + x_2)\star y = (Ax_1 + Ax_2)\cdot Ay$(我们将在后面展示这个性质的应用)

这里的第一、二条很显然,第三条要理解这个变换的实质,而第四条则是第1条的另一个扩展,它在部分情况下很实用。

从 DFT 到 FFT

现在思考我们在DFT中用到的矩阵

发现要计算它还是得 $O(n^2)$ 的时间,我们觉得很恶心,因为这样的变换没有起到降低复杂度的作用。于是我们考虑一个我们已经用过很多遍的技术……算贡献。

然而我们发现……并没有什么卵用。这时候就有人提出,如果让$b_k = b_1^n$的话,事情似乎会变得不一样……

我们发现它依然是可逆的,但是依然没有什么卵用,考虑令 $b = e^{2\pi / n}$

不妨令 $n=8$,我们直观感受一下这个矩阵。

折半引理和蝶形变换

注意到 $b^k = b^{\lfloor k / 2\rfloor}b^{k - 2\lfloor k / 2\rfloor}$ ,我们发现这又是一句废话,但是它非常有用。

然后继续观察矩阵的特征,考虑使用 $X^{[0]}$ 和 $X^{[1]}$ 分别表示这个矩阵分别作用于$x$偶数行和$x$的奇数行的结果。则我们发现,对于结果的前4行,我们有 $X_k = X_k^{[0]} + X_k^{[1]}$ ,对于结果的后四行,我们有 $X_{k+4} = X_{k+4}^{0} - X_{k+4}^{[1]}$

考虑这样的一个计算方法:

注意到这个过程可以递归分治实现,故复杂度为 $O(n \log n)$ ,进一步的分析可以使用非递归的FFT进行计算。

(哇,这又是行又是列的真是绕)

从DFT到NTT

注意到在DFT中,我们使用了单位复数根$e^{2\pi / n}$作为我们的$b$,那么如果要求使用整数,或者说模 $p$ 的群中进行计算的话,有没有别的方法可以达到一样的效果呢?

注意到我们需要这个数满足下面的性质:

  1. $b^{i}$,当$k$取 $i$ 到 $n - 1$ 的时候,值不能有重复。这是为了保证矩阵的线性无关。
  2. $b^{i} + b^{i + n/2} = 0$ ,当然这一点很好满足,因为我们只需要让 $b^{n} = 1 (\mod p)$,即可满足这一点。

那么答案当然是存在的,利用数学中原根的概念,可以很轻易做到这一点。

那么问题就变得非常简单了,只需要简单地用 $p$ 的乘法原根去替换前文中的 $b$ ,我们就可以得到一个新的变换,同时它还满足FFT的几乎所有性质。我们管他叫NTT

(完,这篇文章主要讲了FFT和NTT的各种“为什么”,也是我一直以来比较疑惑的一点。)