多项式乘法

概述

多项式乘法（Polynomial Multiplication）是计算两个多项式乘积的算法问题。两个度数为 $n$ 的多项式相乘，朴素算法需要 $\Theta (n^2)$ 次运算。通过快速傅里叶变换（FFT）方法，利用系数表示与点值表示之间的转换，可在 $\Theta (n\log n)$ 时间内完成。FFT 是多项式乘法的核心加速技术。

定义

多项式乘法（Polynomial Multiplication）

给定两个度数为 $n$ 的多项式：

$A(x)={\sum }_{i=0}^n{a}_i{x}^i,B(x)={\sum }_{i=0}^n{b}_i{x}^i$

其乘积 $C(x)=A(x)\cdot B(x)$ 是一个度数为 $2n$ 的多项式：

$C(x)={\sum }_{k=0}^{2n}{c}_k{x}^k,c_k={\sum }_{i=0}^k{a}_i{b}_{k-i}$

朴素算法直接计算每个 $c_k$，需要 $O(n^2)$ 次乘法。

多项式的两种表示

表示方法	描述	乘法代价
系数表示	$A(x)=(a_0,a_1,\dots ,a_n)$	$\Theta (n^2)$（朴素算法）
点值表示	$\{(x_0,A(x_0)),(x_1,A(x_1)),\dots ,(x_n,A(x_n))\}$	$\Theta (n)$（逐点相乘）

关键洞察：在点值表示下，乘法只需 $\Theta (n)$ 时间。因此，FFT 方法的策略是：

$\text{系数表示}\stackrel{\text{求值 (DFT)}}{\to }\text{点值表示}\stackrel{\Theta (n)}{\to }\text{乘法}\stackrel{\text{插值 (IDFT)}}{\to }\text{系数表示}$

FFT 方法

快速傅里叶变换（FFT）

FFT 利用单位根（roots of unity）的性质，在 $\Theta (n\log n)$ 时间内完成 DFT 和 IDFT：

1. 选择求值点：使用 $2n$ 次单位根 ${\omega }_{2n}^0,{\omega }_{2n}^1,\dots ,{\omega }_{2n}^{2n-1}$ 作为求值点
2. FFT 求值：利用单位根的对称性和分治法，在 $\Theta (n\log n)$ 时间内将系数表示转换为点值表示
3. 逐点相乘：$\Theta (n)$
4. 逆 FFT 插值：$\Theta (n\log n)$

总时间复杂度：$\Theta (n\log n)$

核心性质

性质	描述	备注
朴素复杂度	$\Theta (n^2)$	直接计算卷积
FFT 复杂度	$\Theta (n\log n)$	利用分治 + 单位根
卷积	多项式乘法等价于系数向量的卷积	信号处理的核心运算
分治结构	FFT 的递推关系 $T(n)=2T(n/2)+\Theta (n)$	由主定理情形二得 $\Theta (n\log n)$

应用场景

• 信号处理：数字滤波、频谱分析
• 大整数乘法：将整数视为多项式，用 FFT 加速
• 字符串匹配：通配符匹配、模式匹配
• 图像处理：图像卷积和滤波
• 多项式运算：求值、插值、多项式除法

参见

• 分治法 — FFT 的分治结构
• 主定理 — 分析 FFT 的递推关系
• 递归关系式 — FFT 的递推关系 $T(n)=2T(n/2)+\Theta (n)$
• 动态多线程 — 并行 FFT