第 30 章 多项式与 FFT (Polynomials and the FFT)
核心结论
-
两种多项式表示：系数表示（向量 \(a = (a_0, a_1, \ldots, a_{n-1})\)）便于加减；点值表示 \(\{(x_0, y_0), \ldots, (x_{n-1}, y_{n-1})\}\) 便于乘法（点对点乘）。两种表示一一对应（n 个不同点唯一确定 n 阶多项式）。
-
卷积 (Convolution)：多项式乘法 \(C = A \cdot B\) 等价于系数向量的「卷积」\(c_k = \sum_{j=0}^{k} a_j b_{k-j}\)；朴素算法 Θ(n²)，目标是 Θ(n lg n)。
-
DFT 与 FFT：选「复数 n 次单位根」作为评估点，DFT 把系数表示转为点值表示；FFT 用分治在 Θ(n lg n) 时间实现 DFT 及其逆。
-
FFT 的核心思想：用「偶奇分裂」+「旋转因子」递归地把 n 点 DFT 化为两个 n/2 点 DFT；时间递推 \(T(n) = 2T(n/2) + \Theta(n) = \Theta(n \lg n)\)。
-
快速多项式乘法（定理 30.2）：用 FFT 在 Θ(n lg n) 时间内完成多项式系数乘法——流程：补 0 → FFT 求值 → 点对点乘 → 逆 FFT 插值。
|
本章主旨
FFT 是「用代数结构加速计算」的经典案例——通过选「巧妙的评估点」（单位根）让 DFT 矩阵具备「递归对角化」结构，从而把 Θ(n²) 矩阵-向量乘法降到 Θ(n lg n)。FFT 是信号处理、卷积神经网络、大整数乘法的核心算法。本章三节依次为：多项式表示（系数 vs 点值）、DFT/FFT 推导（单位根性质 + 分治）、高效实现（位反转迭代 + 并行版）。 |
一、核心概念
本章围绕 6 个核心概念展开：从多项式两种表示出发，先介绍卷积与朴素乘法，再定义 DFT 与复数单位根，最后给出 FFT 的递归结构与多项式乘法应用。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
多项式两种表示 |
系数表示 \(a = (a_0, \ldots, a_{n-1})\)；点值表示 \(\{(x_k, A(x_k))\}\)；n 个不同点唯一确定 n-1 阶多项式（定理 30.1）。 |
§30.1；加减法系数表示 Θ(n)；乘法点值表示 Θ(n)。 |
卷积 (Convolution) |
多项式乘法 \(c_k = \sum_{j=0}^k a_j b_{k-j}\)；系数表示朴素 Θ(n²)；点值表示 Θ(n)。 |
§30.1；卷积是信号处理、概率论的核心运算。 |
复数 n 次单位根 |
\(\omega_n = e^{2\pi i/n}\)；n 个单位根 \(\omega_n^0, \omega_n^1, \ldots, \omega_n^{n-1}\) 等距分布单位圆；满足消去 / 对折 / 求和三个引理。 |
§30.2；DFT 矩阵以单位根为元素。 |
离散傅里叶变换 (DFT) |
矩阵形式 \(y_k = \sum_{j=0}^{n-1} a_j \omega_n^{kj}\)；将系数向量 a 转为点值向量 y（在单位根处求值）。 |
§30.2；DFT 矩阵是 Vandermonde 矩阵在单位根处的特例。 |
快速傅里叶变换 (FFT) |
分治算法实现 DFT：偶 / 奇项分离为两个 n/2 点 DFT，合并用「旋转因子」；时间 Θ(n lg n)。 |
§30.2；CLRS 递归版；迭代版用位反转。 |
逆 DFT |
把点值表示转回系数表示；与 DFT 形式相同但用单位根逆 \(\omega_n^{-1}\)；时间 Θ(n lg n) 同 FFT。 |
§30.2；多项式乘法「求值-点乘-插值」的最后一步。 |
二、详细笔记
30.1 多项式的两种表示
What：多项式 \(A(x) = \sum_{j=0}^{n-1} a_j x^j\) 可用「系数向量」或「点值对集合」表示；n 个不同点值对唯一确定 n-1 阶多项式。
Why：不同表示对应不同操作的最优复杂度——系数表示便于加减，点值表示便于乘法；FFT 的核心是「快速切换表示」。
How：
系数表示：\(a = (a_0, a_1, \ldots, a_{n-1})\)；加减法 Θ(n)，乘法 Θ(n²)。
点值表示：\(\{(x_k, y_k)\}_{k=0}^{n-1}\)；加减法 Θ(n)（同点相加减），乘法 Θ(n)（点对点乘）；但乘法结果需 2n 个点（多项式次数 +1）。
唯一性（定理 30.1）：Vandermonde 矩阵在点不同时可逆，故 n 个不同点值对唯一确定 n-1 阶多项式。
朴素 Θ(n²) 算法的局限：系数表示下乘法 Θ(n²)；目标是把 Θ(n²) 降为 Θ(n lg n)。
FFT 加速策略（CLRS 图 30.1）：
-
补 0：把 n 阶多项式扩为 2n 阶（高次系数 0）。
-
求值（FFT）：用 DFT 转为点值（单位根处）。
-
点对点乘：Θ(n)。
-
插值（逆 FFT）：转回系数。
总时间 Θ(n lg n)——关键步骤是求值与插值的 FFT。
When：多项式乘法（朴素 Θ(n²) 不可接受）；卷积运算；信号处理、概率生成函数。
Example：两个 4 阶多项式相乘——朴素需 16 次乘 + 累加；用 FFT 只需 3 次 lg 4 = 6 步 FFT + 8 次点乘。
30.2 复数单位根与 DFT
What：复数 n 次单位根 \(\omega_n = e^{2\pi i/n}\)；n 个根 \(\omega_n^0, \omega_n^1, \ldots, \omega_n^{n-1}\) 等距分布单位圆；DFT 用单位根作为评估点的「求值」操作。
Why：单位根的代数结构（消去 / 对折 / 求和三个引理）使 DFT 矩阵具备递归可分性，是 FFT 分治的基础。
How：
主单位根（式 30.6）：
三个核心引理：
-
引理 30.3（消去）：\(\omega_{dn}^{dk} = \omega_n^k\)。
-
推论 30.4：\(\omega_n^{n/2} = -1\)（n 偶时）。
-
引理 30.5（对折）：n 个 n 次单位根的平方是 n/2 个 n/2 次单位根（各两次）。
-
引理 30.6（求和）：\(\sum_{j=0}^{n-1} \omega_n^{kj} = 0\)（k 非 n 倍数）。
DFT 定义：对系数向量 \(a = (a_0, \ldots, a_{n-1})\)，DFT 在单位根处求值：
逆 DFT：相同形式但用 \(\omega_n^{-1}\)（或 \(\omega_n^{n-k}\)）；最后除以 n。
Vandermonde 矩阵视角：DFT 是「在单位根处的 Vandermonde 求值」，因其特殊结构可分治。
When：FFT 的代数基础；信号处理的频率分析；多项式求值 / 插值的快速算法。
Example：\(\omega_8 = e^{2\pi i/8} = e^{i\pi/4} = \frac{\sqrt{2}}{2}(1 + i)\)；\(\omega_8^4 = -1\)（推论 30.4）。
30.3 FFT 的递归结构
What：FFT 是 DFT 的分治实现——把 n 点 DFT 化为两个 n/2 点 DFT，合并用「旋转因子」；时间 Θ(n lg n)。
Why：朴素 DFT 是矩阵-向量乘法 Θ(n²)；FFT 利用单位根的对折性质把矩阵化为「递归稀疏」结构，从而分治加速。
How：
递归结构：
RECURSIVE-FFT(a)：
-
if n = 1: return a
-
\(\omega_n = e^{2\pi i / n}\)
-
\(y^{(0)} = \text{RECURSIVE-FFT}((a_0, a_2, \ldots, a_{n-2}))\) // 偶下标
-
\(y^{(1)} = \text{RECURSIVE-FFT}((a_1, a_3, \ldots, a_{n-1}))\) // 奇下标
-
for \(k = 0\) to \(n/2 - 1\):
-
\(y_k = y_k^{(0)} + \omega_n^k \cdot y_k^{(1)}\)
-
\(y_{k+n/2} = y_k^{(0)} - \omega_n^k \cdot y_k^{(1)}\)
-
-
return y
正确性（CLRS 定理 30.7）：输出 \(y_k = \sum_{j=0}^{n-1} a_j \omega_n^{kj}\)，即 DFT。
复杂度：递归式 \(T(n) = 2T(n/2) + \Theta(n)\) → 主定理 → \(T(n) = \Theta(n \lg n)\)。
逆 FFT = DFT + 替换 \(\omega_n\) 为 \(\omega_n^{-1}\) + 最后除以 n。
迭代 FFT：位反转（bit-reversal）排序输入，用 for 循环替代递归，常数更小。
When：多项式乘法、卷积、信号处理；大规模 DFT 加速（如 MP3 编码、OFDM 通信）。
Example：n=8 时递归深度 3（lg 8 = 3）；合并步骤 8 次旋转因子乘法；总 ≈ 8·3 = 24 = Θ(n lg n)。
30.4 多项式快速乘法
What：用 FFT 实现两个 n 阶多项式的系数乘法，时间 Θ(n lg n)；流程为「补 0 → FFT 求值 → 点对点乘 → 逆 FFT 插值」。
Why：朴素多项式乘法 Θ(n²) 是数字信号处理、组合数学、机器学习的瓶颈；FFT 把复杂度降到近线性。
How：
完整流程（定理 30.2 证明）：
-
补 0：n 阶多项式 A, B 扩为 2n 阶（高次系数 = 0）。
-
求值：\(\hat A = \text{FFT}(A, 2n)\)、\(\hat B = \text{FFT}(B, 2n)\)；时间 Θ(n lg n)。
-
点乘：\(\hat C_k = \hat A_k \cdot \hat B_k\) for k = 0, …, 2n-1；时间 Θ(n)。
-
插值：\(C = \text{FFT}^{-1}(\hat C) / 2n\)；时间 Θ(n lg n)。
总时间 Θ(n lg n)。
应用：
-
多项式乘法。
-
卷积神经网络 (CNN) 的卷积层。
-
大整数乘法（Schönhage-Strassen 算法）。
-
字符串匹配。
逆 FFT 的实现：直接调用 FFT，把单位根的指数取负 + 最后除以 n。
When：多项式乘法；卷积计算；信号处理（MP3、JPEG、Wi-Fi）；大整数运算。
Example：两个 1024 阶多项式相乘——朴素 10⁶ 次乘，FFT 仅 ~10⁴ 次乘，快 100 倍。
30.5 FFT 的高效实现
What：FFT 的实现有递归版、迭代版（位反转）、并行版（多线程）；迭代版常数更小、缓存更友好；并行版用第 27 章的多线程模型。
Why：不同实现在不同硬件 / 规模下各有优势；理解 trade-off 有助于选型。
How：
迭代 FFT（蝶形网络）：
-
输入按位反转排序：\(a_0, a_4, a_2, a_6, a_1, a_5, a_3, a_7\)（n=8）。
-
多层「蝶形」运算：每层合并相邻 2 个、4 个、8 个……点。
-
时间 Θ(n lg n)，常数比递归版小约 2 倍。
并行 FFT（多线程）：
-
用 spawn 派生子 FFT：work Θ(n lg n)，span Θ(lg n)，并行度 Θ(n)。
-
旋转因子乘法可向量化（SIMD）。
-
适合共享内存多核。
实现工具：
-
FFTW：自适应最快的串行 FFT 库。
-
cuFFT：NVIDIA GPU 上的并行 FFT。
-
Eigen、FFTPACK：经典实现。
实际考量：
-
浮点精度：DFT 可能引入误差；用双精度 / 定点数缓解。
-
实数输入：可利用 Hermitian 对称性节省一半计算。
-
任意长度 n：补 0 到 2^k 即可。
When：实际部署 FFT；性能优化；多核 / GPU 加速。
Example：1M 点 FFT——串行版 ~10ms，GPU 版 ~0.1ms，加速 100 倍。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 30 章 多项式与FFT))
多项式表示
系数表示
点值表示
Vandermonde
唯一性
卷积
朴素Θ(n²)
点值Θ(n)
加速目标
单位根
ωₙ=e^(2πi/n)
消去引理
对折引理
求和引理
DFT
单位根处求值
矩阵形式
逆DFT
FFT
偶奇分裂
旋转因子
Θ(nlg n)
迭代位反转
应用
多项式乘法
卷积
大整数乘法
信号处理五、重点与易错点
-
系数表示 vs 点值表示的「加减 vs 乘法」对称：系数表示利于加减 Θ(n)；点值表示利于乘法 Θ(n)。FFT 在两者间快速切换是核心。
-
Vandermonde 矩阵可逆 ⟺ 点互不相同：这是定理 30.1 的根本；评估点必须互异才能唯一确定多项式。
-
单位根「复数」不可回避：FFT 本质上需要复数；实数输入会产生复数输出；用 Hermitian 对称性可减少存储。
-
三个引理的链：消去 → 对折 → 求和——对折引理最关键，它保证「偶 / 奇项分离后子问题规模减半」。
-
FFT 是分治算法的典范：每轮把 n 点 DFT 拆为两个 n/2 点 DFT + 合并 n 个旋转因子乘法；递推式 T(n) = 2T(n/2) + Θ(n)。
-
补 0 到 2^k：FFT 要求 n 是 2 的幂；不满足时补 0——但多项式乘法需补到 2n 而非最近 2^k，确保次数足够。
-
多项式乘法流程：补 0 → 求值 → 点乘 → 插值。每步时间不同：补 0 Θ(n)、求值 Θ(n lg n)、点乘 Θ(n)、插值 Θ(n lg n)；总 Θ(n lg n)。
-
逆 FFT 的常数因子：直接调用 FFT，把 ω 替换为 ω⁻¹，最后除以 n——常数因子约 2 倍（不用额外算法）。
-
数值精度：FFT 用浮点可能引入误差；用定点或长双精度可缓解；某些应用（如卷积）需要「整数 DFT」(NTT) 完全避免误差。
-
与分治的关联：FFT 是「分治 + 数学结构」的胜利；分治本身需要子问题「形态一致」——单位根的对折性质保证这一点。
-
与第 4 章分治的关联：主定理直接给出 Θ(n lg n)；FFT 是主定理最经典的「case 2」应用（线性合并工作）。
-
与第 27 章多线程的关联：FFT 是「天然并行」的算法；蝶形网络中每层蝶形可并行；并行度 Θ(n)。
-
FFT 应用场景：MP3 / AAC 音频编码、JPEG / MPEG 视频、OFDM 无线通信、卷积神经网络、大整数乘法、密码学（NTRU）。
-
实际工具：FFTW（自适应最优）、cuFFT（GPU）、KissFFT（嵌入式）；Python
numpy.fft、scipy.fft。 -
FFT 不是「万能」：对稀疏数据或非均匀采样点，Lagrange 插值可能更合适；FFT 的 Θ(n lg n) 优势在大 n 时才显著。