FFT(2)

byr 的小窝 / 2024-10-06 / 原文

之前写过 FFT，但是写的有点太垃圾了。

令 $*$ 指代二元运算，一般来说满足交换律和结合律。

FFT 就是当 $*$ 为加法运算时求其卷积。先来探讨一般情况下 $*$ 运算卷积的求法。

实际上，$*$ 卷积就是 $C_k=\sum\limits_{i*j=k}a_ib_j$，直接思考无法得到低于 $O(n^2)$ 的做法。

考虑构造向量到向量的线性变换 $\mathbb{DFT}$，使得经过线性变换后满足 $\mathbb{DFT}(a)_i\times \mathbb{DFT}(b)_i=\mathbb{DFT}(c)_i$，同时其存在可逆变换（等价于刻画该变换的矩阵可逆）$\mathbb{IDFT}$，将 $\mathbb{DFT}(c)$ 经过 $\mathbb{IDFT}$ 重新得到卷积的结果。

将刻画线性变换 $\mathbb{DFT}$ 的矩阵称为 $\mathbb{DFT}$ 矩阵，设为 $A$，将原来的 $a$ 和 $b$ 视作向量的形式 $\vec{u}$ 和 $\vec{v}$，则需要满足：

\[(A\vec{u})_i\times (A\vec{v})_i=(A\vec{w})_i \]

简单推导，$(A\vec{w})_i=\sum\limits_{j}A_{i,j}w_j$，同样有：

\[(A\vec{u})_i=\sum\limits_{j}A_{i,j}u_j \]

\[(A\vec{v})_i=\sum\limits_{j}A_{i,j}v_j \]

根据我们刚才对 $\mathbb{DFT}$ 变换的基本要求，其要满足：

\[(\sum\limits_{j}A_{i,j}u_j)\times(\sum\limits_{j}A_{i,j}v_j)=\sum\limits_{j}A_{i,j}w_j \]

\[\sum\limits_{j}\sum\limits_{k}A_{i,j}A_{i,k}u_jv_k=\sum\limits_{j}A_{i,j}w_j \]

如果将 $w_j$ 重新拆成一开始的卷积形式：

\[\sum\limits_{j}\sum\limits_{k}A_{i,j}A_{i,k}u_jv_k=\sum\limits_{j}\sum\limits_{k}A_{i,j*k}u_jv_k \]

关于后面那个式子，实际上就是卷积的两种形式的转化。

根据一些与形式幂级数类似的经典结论，得到：

\[A_{i,j}A_{i,k}=A_{i,j*k} \]

对于满足 $A_{i,j}A_{i,k}=A_{i,j*k}$ 且可逆的矩阵称为 $\mathbb{DFT}$ 矩阵。

加法卷积中的 $\mathbb{DFT}$ 矩阵

FFT 中 $*$ 就是数域上的加法运算，上述结论立刻得到 $A_{i,j}A_{i,k}=A_{i,j+k}$。

一种平凡的构造是 $A_{i,j}=a^j$，此时上述结论成立但该矩阵行列式值为 $0$，不可逆，无法进行 $\mathbb{IDFT}$ 变换。

稍微进行改动，取 $A_{i,j}=a^{ij}$，这样性质依旧存在且可逆。

神秘地令 $a=\omega_n$，即 $A_{i,j}=\omega_n^{ij}$。

将该矩阵称为范德蒙德矩阵。

考虑其逆矩阵（刻画 $\mathbb{IDFT}$ 的矩阵），有一种充满人类智慧的构造：

观察 $(A\times A)_{i,j}=\sum\limits_{k}A_{i,k}A_{k,j}=\sum\limits_{k}\omega_n^{k(i+j)}$，应用等比数列求和公式 $\dfrac{a_1-a_nq}{1-q}$，得到 $\dfrac{1-\omega_n^{n(i+j)}}{1-\omega_n^{i+j}}$。类似地，构造 $B_{i,j}=\omega_n^{-ij}$，得到 $(A\times B)_{i,j}=\dfrac{1-\omega_n^{n(i-j)}}{1-\omega_n^{i-j}}$，惊人的发现，$\dfrac{1}{n}AB$ 是一个单位矩阵！于是，范德蒙德逆矩阵就是 $\dfrac{1}{n}B$。

FFT

现在已经有了范德蒙德矩阵：$A_{i,j}=\omega_n^{ij}$，则 $(A\vec{u})_i=\sum\limits_{j}\omega_n^{ij}\vec{u}_j$，从多项式的角度构造 $f(x)=\sum\limits_{j}\vec{u}_jx^j$，则 $(A\vec{u})_i=f(\omega_n^i)$。