大致结构:本篇文章主要讲解 FFT,另外一个文章再详细讲解矩阵乘法
flowchart LR
classDef main fill:#2f6f8f18,stroke:#2f6f8f,stroke-width:1.5px
classDef bridge fill:#b0612a18,stroke:#b0612a,stroke-width:1.5px
classDef loop fill:#4f8a4b18,stroke:#4f8a4b,stroke-width:1.5px,stroke-dasharray: 4 3
Conv["卷积 = 多项式乘法<br/>O(N²) 交叉项"]:::main
Roots["复数 · 欧拉公式 · 单位根<br/>正交性 + 折半对称"]:::bridge
DFT["DFT / 傅里叶变换<br/>卷积 → 逐点相乘"]:::main
FFT["FFT O(N log N)<br/>与零误差 NTT"]:::main
Circ["循环矩阵对角化<br/>F C_b F⁻¹ = diag"]:::main
Strassen["一般矩阵失灵<br/>Strassen 与张量秩"]:::bridge
Paper["9/4 论文<br/>多项式张量上下夹逼"]:::loop
Conv -->|"换点值坐标系"| Roots --> DFT
DFT -->|"补零 + 蝶形分治"| FFT
DFT -->|"线性代数视角"| Circ
Circ -->|"失去平移对称性"| Strassen --> Paper
Roots -.->|"单位根求和再次充当筛子"| Paper
mermaid
约定:文中的离散序列默认从下标 0 开始,未写出的项视为 0;离散傅里叶变换(DFT)使用负指数作为正变换,正指数并除以 N 作为逆变换(不同教材正负号可能对调,只要正逆配对即可)。
你可以按四幕顺序通读,前三幕构成卷积与 FFT,第四幕延伸至矩阵乘法与前沿研究:
- 第一幕:从 音乐厅的余音 走到 多项式乘法,看清 O(N2) 交叉项的来源。
- 第二幕:经由 点值表示、复数、欧拉公式 与 单位根,理解 傅里叶变换 与 DFT。
- 第三幕:理清 循环卷积与补零、FFT 蝶形与位反转,以及模数世界里的 NTT。
- 第四幕:从 循环矩阵对角化 切入 Karatsuba 与 Strassen、张量秩与边界秩,最后读懂 9/4 论文的核心构造。
卷积的理解#
在音乐厅里,一个音结束了,它留下的影响却未必结束。
新的琴声不断响起,旧的琴声还在墙壁和穹顶之间来回反射。听众此刻听到的,是过去所有声音经过音乐厅改造后、在当前时刻叠在一起的结果。
卷积描述的正是这个过程:每一次输入都在时间里拖出一条尾巴,所有尾巴在当前时刻相遇,叠成此刻的输出。
现在我们请出三个角色:演奏家、音乐厅、听众。
一个音与它的余音#
在音乐厅里轻轻敲一下琴键,声音响起,随后渐渐消散。
我们先做一个理想化的简化:把这次按键当成瞬间发生、强度为 1 的“标准一下”。 按键本身短促得像个点,但音乐厅不会立刻安静下来——把音乐厅对这“标准一下”的响应曲线记作 h(t),其中 t 表示从按键那一刻算起,已经过去了多久。
同样敲一下,放进浴室、空教室、大音乐厅,拖出来的尾巴 h(t) 各不相同。
当然,前提是这间音乐厅守两条规矩:
- 时不变:同样一下琴声,晚 3 秒敲,余音也只是原封不动地晚 3 秒出现,不会因为过了中午就变调。
- 线性:按键力度放大 a 倍,余音也按比例放大 a 倍;先后敲两下琴键,厅里的声音就是两段余音直接相加。
满足这两条规矩的系统,叫线性时不变系统(LTI)。
左:单位冲激输入对应的响应曲线 h(t);右:多次按不同力度和时刻触发的余音按线性时不变规则平移、缩放并叠加。
为什么要翻转#
刚学卷积时,我们大概会被课本上“先把 h(τ) 翻转成 h(−τ),再平移成 h(t−τ)”绕晕:好端端的声音传播,怎么还带倒着走的?
声音并没有倒着走,只是我们从演奏家的琴凳,换到了听众席的座位上。
先坐到演奏家的位置上。假设整首曲子由一串短促的按键组成,第 k 次按键发生在 τk 时刻,力度是 ak。到了后来的 t 时刻,这次按键已经过去了 t−τk 这么久,它在厅里留下的余音自然是:
akh(t−τk).
把所有按键拖出来的余音叠在一起,就是听众在 t 时刻听到的总声音:
y(t)=k∑akh(t−τk).
现在换到听众席。听众不关心某个音未来去哪儿,只关心此时此刻 t,我耳朵里听到的声音是从过去哪些时刻凑出来的?
固定住现在的时刻 t,沿着输入时间轴 τ 往回盘点:
- 越是刚刚敲响的音(τ 越靠右、越贴近 t),它在空气里飘的时间 t−τ 越短,要查响应说明书 h 靠左的开头部分;
- 越是老早以前敲响的音(τ 越靠左、离 t 越远),它飘的时间 t−τ 反而越长,要查 h 靠右的尾巴部分。
输入时刻 τ 往右走,经过的时间 t−τ 在往左缩。
所以,当我们把响应曲线画在“输入时刻 τ”这条横轴上时,曲线的朝向自然就掉了个头:
h(τ)掉头往回看h(−τ)站在时刻 t 盘点h(t−τ).
站在听众时刻 t 回头沿输入轴 τ 盘点:τ 越靠近 t,经过的时间 t - τ 越短,因此响应曲线在 τ 轴上呈现为翻转并平移后的 h(t - τ)。
所谓“翻转、平移”,并非物理世界里有什么东西倒转了,即站在当前时刻 t 回头清点时,离现在越近的输入,对应持续作用的时间越短。
连续声音#
如果演奏的不是顿音,而是一段连绵不断的小提琴声 x(t) 呢?
办法依然朴素:把时间轴切成许多宽度为 Δτ 的小薄片。只要切得够薄,τk 附近那一小片的声音强度几乎不变,整片的“份额”就是高度乘宽度 x(τk)Δτ。
把连续输入 x(τ) 切成宽度为 dτ 的薄片,每一薄片视作权重为 x(τ)dτ 的瞬时冲激,各自拖出按比例缩放的余音并积分叠加。
把这一小片当成一次权重为 x(τk)Δτ 的瞬间敲击,它在 t 时刻留下的贡献就是 x(τk)h(t−τk)Δτ。把所有时间薄片的贡献加起来,再让薄片宽度 Δτ→0,求和号就变成了积分号:
y(t)=(x∗h)(t)=∫−∞+∞x(τ)h(t−τ)dτ.
在真实的音乐厅里,未来的声音还没发出,不会影响现在(即当 τ>t 时 h(t−τ)=0,称为因果性),所以积分上限写到 t 就够了。
展开查看:用单位冲激δ(t) 写出的四步推导
如果用广义函数里的狄拉克 δ 函数(宽度压到 0、高度撑到无穷、但面积恒为 1 的理想尖峰),任何连续信号 x(t) 都可以写成无数个尖峰的加权叠加(筛选性质):
x(t)=∫−∞+∞x(τ)δ(t−τ)dτ.把它送进线性时不变系统,只需四步就能直接写出卷积公式:
- 标准一下的定义:δ(t)⟼h(t)
- 时不变(推迟 τ):δ(t−τ)⟼h(t−τ)
- 线性缩放(乘常数 x(τ)):x(τ)δ(t−τ)⟼x(τ)h(t−τ)
- 线性叠加(对所有 τ 积分):∫x(τ)δ(t−τ)dτ⟼∫x(τ)h(t−τ)dτ=y(t)。
(注:在数学上把系统算子搬进积分号内部,需要信号与响应满足适当的连续性或可积性条件,例如 x,h∈L1(R);更完整的背景可参考 MIT 6.003 课程讲义 ↗,本节音乐厅的叙事灵感参考自 B 站上的这期卷积漫谈视频 ↗。)
把连续时间换成离散的格子,就会更易理解了。
假设一个极简音乐厅:敲一下强度为 1 的音,当前这一格响 1,下一格留 0.5 的余音,再往后归零,即 h=[1,0.5]。
我们在第 0 格和第 1 格连续敲两下,力度分别是 2 和 3(x=[2,3]):
- 第 0 格:只有第一次按键刚响起,输出 2×1=2;
- 第 1 格:第一次按键留下的余音 2×0.5=1,撞上第二次按键的新声音 3×1=3,叠出 4;
- 第 2 格:只剩第二次按键的余音 3×0.5=1.5。
[2, 3]∗[1, 0.5]=[2, 4, 1.5].
中间那个 4 即新的到了,旧的还在。
按下标之和配对的理解#
把刚才的手算写成通用的离散序列公式。设输入序列为 a,系统响应为 b,输出序列的第 k 项是:
ck=(a∗b)k=j∈Z∑ajbk−j.
盯住 aj 和 bk−j 脚底下的两个下标看一眼:
j+(k−j)=k.
换句话说,离散卷积做的唯一一件事,就是把所有“下标加起来等于 k”的成对乘积 aibj 统统收进同一个篮子里,加起来交给 ck。
ck=i+j=k∑aibj.
取 a=[1,2,3],b=[4,5,6]。按“下标之和等于 k”分拣全部 3×3=9 个乘积:
c0c1c2c3c4=a0b0=1⋅4=4,=a0b1+a1b0=1⋅5+2⋅4=13,=a0b2+a1b1+a2b0=1⋅6+2⋅5+3⋅4=28,=a1b2+a2b1=2⋅6+3⋅5=27,=a2b2=3⋅6=18.
所以 [1,2,3]∗[4,5,6]=[4,13,28,27,18]。
c2=∑i+j=2aibj=a0b2+a1b1+a2b0=1⋅6+2⋅5+3⋅4=28
A(x)B(x)=(1+2x+3x2)(4+5x+6x2)=4+13x+28x2+27x3+18x4
普通卷积的长度是 3+3−1=5。把下面的 N 拉到 5 或更大,循环卷积就和它完全一样;小于 5 时,末尾的项会绕回开头。
注意结果的长度:两个长度分别为 n 和 m 的序列,最大下标是 n−1 和 m−1,加起来最远走到 n+m−2。从 0 数到 n+m−2,一共会有 n+m−1 个篮子(这个数字后面做补零时会反复用到)。
按下标之和装篮的结构在概率论里也很常见:掷两颗独立的六面骰子,ai 和 bj 是各自掷出 i,j 点的概率,那么“点数之和等于 k”的总概率就是把所有 i+j=k 的联合概率 aibj 加起来——独立随机变量之和的分布,天然就是它们各自概率分布的卷积。
多项式与卷积#
现在回答开篇的第一个问题:音乐厅里的余音,怎么会跟多项式乘法撞在一起?
刚才我们已经看清,卷积的核心动作是:只要 i+j=k,就把 aibj 归入第 k 号篮子。而在初中学过的代数运算里,天生满足“相乘时脚标自动相加”的,正是指数运算:xi⋅xj=xi+j。
给序列 a=[a0,a1,…,an−1] 的每一项贴上一张写着 xi 的标签,拼成多项式:
A(x)=a0+a1x+a2x2+⋯+an−1xn−1,
同样把 b 写成 B(x)=∑jbjxj。按分配律乘开、合并同类项:
A(x)B(x)=(i∑aixi)(j∑bjxj)=k∑i+j=k∑aibjxk.
xk 前面的系数就是离散卷积 ck:
(1+2x+3x2)(4+5x+6x2)=4+13x+28x2+27x3+18x4.
在这里不必把 x 当成急着代数字求值的“未知数”。在生成函数眼里,x 更像一个占位符:xi 负责记住 ai 原来坐在第 i 号位置,并在相乘时靠指数加法 xixj=xi+j 自动把乘积送进第 i+j 号位置。
交叉项带来的瓶颈#
不管叫离散卷积还是多项式乘法,只要按定义直接算,每个 ai 都得和每个 bj 相乘一次。两个长度为 N 的序列卷在一起,总共要做 N2 次乘法。
当 N=105 时,N2=1010,直接算显然吃不消。于是核心问题浮出水面:
输出一共只有 2N−1 项,我们真的必须把中间那 N2 个交叉乘积 aibj 逐个算出来吗?能不能换个坐标系,让两边“各乘各的”?
点值表示的诱惑与困境#
想避开“项与项两两交叉”,代数里早就有一条捷径:点值表示。
一条抛物线 C(x)=c0+c1x+c2x2,可以用三个系数 (c0,c1,c2) 描述,也可以在横轴上任取 3 个不同的点(比如 x=0,1,2),用它的三个高度 (C(0),C(1),C(2)) 描述。
一般地,一个次数小于 N 的多项式,由它在 N 个互不相同的点 x0,x1,…,xN−1 上的取值唯一确定(因为两个次数小于 N 的不同多项式相减,最多只能有 N−1 个根,不可能在 N 个点上全相等)。
一旦换到点值表示,原本 O(N2) 的交叉相乘变成了 O(N) 的逐点相乘:
C(xk)=A(xk)⋅B(xk),k=0,1,…,N−1.
在第 k 个点上,A(xk) 只跟 B(xk) 相乘,与其他点完全无关——交叉项消失了。
换坐标系的代价#
既然这么省事,为什么不随便挑 x=0,1,2,…,N−1 算完呢?因为“换坐标系”本身是要付代价的:
flowchart LR
classDef slow fill:#b0612a14,stroke:#b0612a,stroke-dasharray: 4 3
classDef fast fill:#2f6f8f18,stroke:#2f6f8f,stroke-width:1.5px
In["系数表示<br/>a, b"]:::fast
Out["乘积系数<br/>c = a * b"]:::fast
PV1["点值 / 频域<br/>â = F·a, b̂ = F·b"]:::fast
PV2["逐点乘积<br/>ĉ = â ⊙ b̂"]:::fast
In -.->|"直接卷积:O(N²) 交叉乘加<br/>(矩阵视角:C_b · a)"| Out
In -->|"1. 求值 FFT<br/>O(N log N)"| PV1
PV1 -->|"2. 逐点相乘<br/>O(N) · diag(b̂)"| PV2
PV2 -->|"3. 插值 IFFT<br/>O(N log N) · F⁻¹"| Out
mermaid
(这张图,在第四幕的循环矩阵里会和 Cba=F−1diag(b)Fa 严丝合缝地重合。)
如果随便挑 N 个点,把一个 N 项多项式代进 1 个点要算 O(N) 次,代进 N 个点就要 O(N2) 次;算完再插值回系数(解范德蒙德方程组)直接算又是 O(N2),而且实数等距点的幂次 2N,3N 增长极快,会把范德蒙德矩阵的条件数推向指数级恶化,稍微有点浮点舍入就会让插值严重失真。
3 个点值确定次数 <3 的多项式:插值得到 3+10x+8x2=C(x)
| xj | A(xj) | B(xj) | A(xj)B(xj) |
| −1.5 | −2 | −3 | 6 |
| −0.5 | 0 | 1 | 0 |
| 0.5 | 2 | 5 | 10 |
点值表示下,乘法只是把同一行的两个数相乘,3 个点就做 3 次乘法。C 的次数是 2,3 个点已经够用;多出来的点只是重复确认同一个多项式。
插值有多稳:范德蒙德矩阵的条件数 κ2(V)
| 点数 n | 本图的实数点 | xj=0,1,…,n−1 | 单位根 |
| 2 | 1.6 | 2.6 | 1 |
|---|
| 3 | 5.6 | 13.9 | 1 |
|---|
| 4 | 21.9 | 154 | 1 |
|---|
| 6 | 424 | 5.77×10⁴ | 1 |
|---|
| 8 | 9539 | 5.29×10⁷ | 1 |
|---|
| 12 | 6.00×10⁶ | 2.46×10¹⁴ | 1 |
|---|
| 16 | 4.37×10⁹ | >10¹⁵ | 1 |
从点值解出系数,就是解方程 Vc=y,其中 Vjp=xjp。固定精确的 V、仅扰动右端点值时,系数向量在 2 范数下的相对误差至多是点值相对误差的 κ2(V) 倍。这里的条件数描述最坏方向的敏感性,不表示每组数据都会损失对应位数,也不保证每个系数的相对误差。
单位根的 V 是傅里叶矩阵 F,满足 F∗F=NI,因此 F/N 是酉矩阵且 κ2(F)=1:上述范数相对误差不会因这个线性问题被放大。计算单位根、执行变换与逐点乘法仍有浮点舍入误差;大条件数的表值本身也只是双精度估计。现在的 3 个实数点,估计条件数为 5.6。
现在等于原地踏步… 所以真正的问题变成:
能不能挑一组特殊的采样点 x0,…,xN−1,让它们之间存在对称关系——算出前一半点的值,后一半就能顺手复用?
把多项式按偶数次项和奇数次项拆开,就能看出我们需要什么样的点:
A(x)=(a0+a2x2+a4x4+⋯)+x(a1+a3x2+a5x4+⋯)=E(x2)+xO(x2).
右边的 E(⋅) 和 O(⋅) 吃的都是 x2。只要我们挑的 N 个点两两互为相反数 (x,−x),平方之后 N 个点就会坍缩成 N/2 个不同的平方值 x2,问题规模减半。
可是在实数轴上,这招只能用一次:第一次挑 ±1,±2,±3,±4,平方之后变成 1,4,9,16——全是正数。下一层还想找互为相反数的点,就得要求某个数满足 z2=−正数。
实数轴太窄了,一下子就撞上了平方非负的墙。 要想一路对半折上 log2N 次,我们只能走出实数轴,去请出平方等于 −1 的数。
乘以 i 的意义#
方程 x2=−1 在实数轴上无解。引入虚数单位 i,规定
i2=−1,
再把所有形如 z=a+bi(a,b∈R)的数合称复数,画在二维平面上的点 (a,b)。它的模长是 ∣z∣=a2+b2,共轭是 z=a−bi,两者相乘消掉虚部:zz=a2+b2=∣z∣2。
但如果只把 i 当成一个死记硬背的符号,就错过了复数最漂亮的地方。算一下把平面上的点 (a,b) 乘上 i 会怎样:
i(a+bi)=−b+ai.
原来的向量 (a,b) 变成了 (−b,a):长度不变,方向刚好逆时针转了 90∘。
1×ii×i−1×i−i×i1.
这样看,i2=−1 就非常自然了:乘一次 i 是逆时针转 90∘,连乘两次转 180∘,自然掉头指向反方向的 −1。
长度相乘,角度相加#
把任意两个复数写成极坐标(模长 r,s、夹角 θ,ϕ):
z=r(cosθ+isinθ),w=s(cosϕ+isinϕ).
直接乘开,套用三角函数的和角公式:
zw=rs[(cosθcosϕ−sinθsinϕ)+i(sinθcosϕ+cosθsinϕ)]=rs(cos(θ+ϕ)+isin(θ+ϕ)).
复数乘法的几何本质就八个字:模长相乘,角度相加。
特别是当你乘上一个模长 r=1(落在单位圆上)的复数时,它不改变原向量的长度,是一个纯粹的旋转算子。
左:乘以 i 等价于逆时针旋转 90°;右:一般复数相乘将模长相乘、辐角相加。
∣z∣∣w∣=1.58×1.17=1.84=∣zw∣,argz+argw=18.4∘+59∘≡77.5∘
z=1.5+0.5i
w=0.6+i
zw=0.4+1.8i
淡色的单位方格和字母 F 是原图;实线是它们乘以 z 之后的样子。整个平面被同一个复数旋转并缩放,方格依旧是方格:乘法不会把平面拉歪。
欧拉公式#
每次写 cosθ+isinθ 还是偏啰嗦。既然“两个单位复数相乘,等于把它们的角度 θ 和 ϕ 相加”,而在基础数学里,天生满足“函数值相乘 = 自变量相加”的,又是指数函数 eA⋅eB=eA+B。
把复指数 eiθ 代进实数指数函数的泰勒幂级数 ez=∑n=0∞n!zn,按偶数项和奇数项分组(利用 i2=−1,i3=−i,i4=1 每四步一循环):
eiθ=(1−2!θ2+4!θ4−⋯)+i(θ−3!θ3+5!θ5−⋯)=cosθ+isinθ.
这就是欧拉公式(MIT 18.03 复数与指数讲义 ↗给出了更多几何视角)。
大家平时常感叹它的特例 eiπ+1=0,但在算法与信号处理里,它真正的威力在于:它把平面上的旋转角度 θ 直接放进了指数的肩膀上。
- ∣eiθ∣=cos2θ+sin2θ=1:只要指数是纯虚数 iθ,它就待在单位圆上,角度为 θ;
- eiαeiβ=ei(α+β)
- 把 eiθ 和共轭 e−iθ 相加相减:
cosθ=2eiθ+e−iθ,sinθ=2ieiθ−e−iθ.
单位根*#
铺垫完复数和欧拉公式,现在回到“点值表示”结尾的死结:去哪儿找 N 个点,能让它们平方之后数量减半、还能一路对半折下去?
答案在单位圆上。方程
zN=1
要找的是连着自乘 N 次(角度连翻 N 倍)后刚好转回 1 的复数。把一整圈 2π 平均切成 N 份,记顺时针转一份的基本步长为:
ωN=e−2πi/N,
那么它的 0,1,…,N−1 次幂:
ωN0, ωN1, ωN2, …, ωNN−1
像切披萨一样把单位圆均匀分成 N 个点,叫作 N 次单位根(其中 ωN 走满 N 步才第一次回到 1,叫本原 N 次单位根)。
当 N 是偶数时,这组点同时满足三条极好用的性质:
- 周期性:ωNk+N=ωNk。
- 对称性:ωNk+N/2=ωNk⋅e−πi=−ωNk。相隔半圈的两个点,天然互为相反数。
- 折半性:平方之后,自动落到半圈规模的单位根上:
(ωNk)2=(ωN2)k=(e−2πi/(N/2))k=ωN/2k.
拿 N=4 试一下:ω4=−i,四个 4 次单位根是 (1,−i,−1,i)。全部平方后变成 (1,−1,1,−1)——只剩 (1,−1) 两个 2 次单位根;再平方一次,只剩 1 这个 1 次单位根。把 N=8 的平方坍缩过程画出来,它正好与后文的“位反转分治树”互为镜像:
flowchart LR
classDef n8 fill:#2f6f8f18,stroke:#2f6f8f,stroke-width:1.4px
classDef n4 fill:#2f6f8f10,stroke:#2f6f8f
classDef n2 fill:#b0612a14,stroke:#b0612a
classDef n1 fill:#4f8a4b18,stroke:#4f8a4b,stroke-width:1.5px
subgraph L8["N = 8(8 个点)"]
w80["ω₈⁰ = 1"]:::n8
w84["ω₈⁴ = -1"]:::n8
w81["ω₈¹"]:::n8
w85["ω₈⁵ = -ω₈¹"]:::n8
w82["ω₈² = -i"]:::n8
w86["ω₈⁶ = i"]:::n8
w83["ω₈³"]:::n8
w87["ω₈⁷ = -ω₈³"]:::n8
end
subgraph L4["N = 4(4 个点)"]
w40["ω₄⁰ = 1"]:::n4
w41["ω₄¹ = -i"]:::n4
w42["ω₄² = -1"]:::n4
w43["ω₄³ = i"]:::n4
end
subgraph L2["N = 2(2 个点)"]
w20["ω₂⁰ = 1"]:::n2
w21["ω₂¹ = -1"]:::n2
end
w10["1"]:::n1
w80 & w84 -->|"z²"| w40
w81 & w85 -->|"z²"| w41
w82 & w86 -->|"z²"| w42
w83 & w87 -->|"z²"| w43
w40 & w42 -->|"z²"| w20
w41 & w43 -->|"z²"| w21
w20 & w21 -->|"z²"| w10
mermaid
在实数轴上折一刀就撞墙的奇偶配对,在单位圆上因为可以“转圈”,不管 N=2s 有多大,都能一路平方、一路对半折到底。而且它们模长恒为 1、彼此正交,构成的傅里叶矩阵 2-范数条件数恒为 1,也顺手避开了实数等距点插值时的数值失控。
单位根的正交求和#
单位根还有一条贯穿后文(DFT 逆变换乃至 9/4 论文)。任取整数 r:
j=0∑N−1ωNjr={N,0,若 N∣r,若 N∤r.
证明:
- 若 N∣r,每一项都是 ωNr=1,N 个 1 相加得 N;
- 若 N∤r,公比 q=ωNr=1 且 qN=1,等比数列求和 1−q1−qN=0。
直觉:当 N∤r 时,这 N 个单位向量在圆周上均匀分布,像 N 个人围成一圈朝四面八方拉绳子,合力严格抵消为 0;只有大家朝同一个方向(N∣r)使劲时,合力才会累加出 N。
「合拍得 N、不合拍归 0」
左:8 次单位根均匀分布在单位圆上,关于原点对称的点互为相反数;右:非平凡步长下,8 个单位向量首尾相接围成闭合正多边形,总和严格为 0。
复指数:卷积的特征函数#
在进入离散算法之前,回看一下连续信号:为什么信号处理总是围绕 e2πift 打转?
把频率为 f 的纯旋转信号 x(t)=e2πift 送进冲激响应为 h(τ) 的音乐厅里,计算输出 y(t):
y(t)=∫−∞∞h(τ)x(t−τ)dτ=∫−∞∞h(τ)e2πif(t−τ)dτ=H(f)(∫−∞∞h(τ)e−2πifτdτ)⋅e2πift=H(f)e2πift.
能把 e2πif(t−τ) 拆成 e2πift⋅e−2πifτ 并提出积分号外,靠的依然是指数把时间加减变成了乘法。而结果非常耐人寻味:
随便送一段波形进音乐厅,出来的波形通常面目全非;但如果送进去的是复指数 e2πift,出来的依然是同样频率的 e2πift,只是整体乘了一个复常数 H(f)(振幅缩放 ∣H(f)∣ 倍,相位平移 argH(f))。
复指数 e2πift 是所有线性时不变系统的公共特征函数,H(f) 就是对应的特征值。 如果能把任意信号拆成单频复指数的叠加,卷积就会退化成按频率逐点相乘。
傅里叶变换#
怎么把一段混杂的信号 x(t) 拆成各个频率的分量?靠的还是正交抵消。
在区间 [0,T] 上,不同整数圈数的复指数 ek(t)=e2πikt/T 彼此正交:
T1∫0Tek(t)eℓ(t)dt=T1∫0Te2πi(k−ℓ)t/Tdt={1,0,k=ℓ,k=ℓ.
想知道信号 x(t) 里含有多少频率 k/T 的成分,只需拿一根反向旋转的探针 e−2πikt/T 乘上去,再对一个周期求平均:
- 信号里以 +k 圈旋转的成分,被探针的 −k 圈抵消了旋转,定格成常数,积分留住;
- 其他频率 ℓ=k 的成分仍在绕原点旋转,转满整数圈后积分抵消为 0。
把频率为 3 的信号绕在复平面原点上:当探针频率不匹配时(中),曲线围绕原点对称分布,质心归零;当探针频率与信号合拍时(右),波峰全部朝向同一侧,质心明显偏离原点。
这个地方 3b1b 形象展示傅里叶变换的视频 ↗ 讲的很好
当区间推向整条实数轴,离散频率变成连续频率 f,就得到连续傅里叶变换与逆变换:
x(f)=∫−∞∞x(t)e−2πiftdt,x(t)=∫−∞∞x(f)e2πiftdf.
对卷积 (x∗h)(t) 做变换,令 u=t−τ(t=u+τ),指数把位置相加拆成乘积,双重积分自然裂成两个独立积分之积(卷积定理):
x∗h(f)=x(f)⋅h(f).
直观例子:两个方波卷出三角形
取 [0,1] 上高度为 1 的矩形脉冲 p(t)。在时域里,(p∗p)(t) 是滑动区间 [t−1,t] 与 [0,1] 的重叠长度,是一条从 0 爬到 1 再降回 0 的三角形曲线。而在频域里,p(f)=e−πifπfsin(πf),三角形脉冲的傅里叶变换无需再算积分,直接平方就是 p(f)2。
(注:连续积分变换的严格存在性与反演条件通常在 L1(R) 或 Schwartz 函数空间中讨论,可参阅华盛顿大学傅里叶讲义 ↗。)
DFT#
回到计算机里,我们手里只有长度为 N 的有限序列 a0,a1,…,aN−1。
把连续积分换成有限求和,把探针换成 N 次单位根 ωN=e−2πi/N,就得到了离散傅里叶变换(DFT):
ak=j=0∑N−1ajωNjk,k=0,1,…,N−1.
对照前面写的多项式 A(x)=∑j=0N−1ajxj,就会看到:
ak=A(ωNk).
信号处理里的离散傅里叶变换(DFT)就是把多项式 A(x) 代入全部 N 个单位根 ωN0,ωN1,…,ωNN−1 算出的点值表示。
逆变换#
已知 N 个单位根上的点值 a0,…,aN−1,怎么把原来的系数 ar 捞回来?不必去解复杂方程组,直接用单位根正交求和——把每个 ak 乘上反向旋转的 ωN−kr 加起来:
k=0∑N−1akωN−kr=k=0∑N−1(j=0∑N−1ajωNjk)ωN−kr=j=0∑N−1aj仅 j=r 时为 N,其余为 0(k=0∑N−1ωNk(j−r))=Nar.
两边除以 N,逆变换直接出现:
ar=N1k=0∑N−1akωN−kr.
逆 DFT 和正 DFT 结构几乎完全对称,只是把 ωN 换成共轭反方向 ωN−1,最后除以 N。所以写一个正变换加速(FFT),改个符号就能直接跑逆变换。
取 a=[1,2,0,0],对应 A(x)=1+2x。代入 4 次单位根 (1,−i,−1,i):
a0=A(1)=3,a1=A(−i)=1−2i,a2=A(−1)=−1,a3=A(i)=1+2i.
a1=1−2i 和 a3=1+2i 互为共轭。因为在整数采样点 j 上,顺时针转 N−k 格(ωN(N−k)j)和逆时针转 k 格(ωN−kj=ωNkj)重合。对任何实数序列都有 aN−k=ak,后半段编号 k>N/2 的频点其实就是负频率 k−N。
循环卷积#
如果拿两个长度为 N 的序列 a,b,各自做 DFT 得到 ak,bk,逐点相乘 ck=akbk,再做逆 DFT 回来,得到的是普通卷积吗?
未必。展开 C(x)=A(x)B(x),最高次数可达 2N−2。但在 N 次单位根上,(ωNk)N=1,所有次数达到或超过 N 的项都会折返:
(ωNk)N+r=(ωNk)N⋅(ωNk)r=(ωNk)r.
在 N 次单位根眼里,xN+r 和 xr 无法区分。原本属于第 N+r 号位置的系数 cN+r 会绕回来,叠加到第 r 号位置上:
ckcyc=j=0∑N−1ajb(k−j)modN=ck+ck+N+ck+2N+⋯
这就是循环卷积。以 a=[1,2,3],b=[4,5,6] 为例,普通卷积有 5 项:[4,13,28,27,18]。若只用长度 N=4 的 DFT 去算,18x4 会按 x4=1 折回常数项,算出 [4+18,13,28,27]=[22,13,28,27]——即循环混叠:
flowchart LR
classDef ok fill:#2f6f8f18,stroke:#2f6f8f,stroke-width:1.4px
classDef wrap fill:#b0612a18,stroke:#b0612a,stroke-width:1.6px,stroke-dasharray: 4 3
classDef hit fill:#b0612a22,stroke:#b0612a,stroke-width:1.8px
subgraph Lin["线性卷积结果(5 项)"]
L0["c₀ = 4"]:::ok
L1["c₁ = 13"]:::ok
L2["c₂ = 28"]:::ok
L3["c₃ = 27"]:::ok
L4["c₄ = 18(x⁴ 项)"]:::wrap
end
subgraph Cyc["长度 N = 4 的循环槽位"]
C0["槽位 0:4 + 18 = 22"]:::hit
C1["槽位 1:13"]:::ok
C2["槽位 2:28"]:::ok
C3["槽位 3:27"]:::ok
end
L0 --> C0
L1 --> C1
L2 --> C2
L3 --> C3
L4 -.->|"x⁴ = 1 绕回碰撞"| C0
mermaid
避免绕回#
原因很简单:结果有 n+m−1 项,篮子只有 N<n+m−1 个,溢出了。
只要事先选变换长度 N≥n+m−1,把两个输入序列末尾都补上 0 扩充到长度 N,乘积中就不会出现次数 ≥N 的非零项,自然没有任何项会绕回来。
两个长度为 3 的序列相乘,结果有 5 项;配合基 2 FFT 选最小的 2 的幂 N=8 补零,循环卷积算出的前 5 项就和普通卷积完全一致。
代数视角:多项式环上的中国剩余定理
在单位根上求值,等价于把多项式对 xN−1=∏k=0N−1(x−ωNk) 取模。由中国剩余定理,商环分解为 N 个独立复数域的直积:
C[x]/(xN−1)≅k=0∏N−1C[x]/(x−ωNk)≅CN,[A(x)]⟼(A(1),A(ωN),…,A(ωNN−1)).左边的乘法是模 xN=1 的循环卷积,右边是逐坐标相乘,而连接两边的同构映射正是 DFT。
FFT#
现在可以把前面为单位根埋下的伏笔全部兑现了。快速计算 DFT 的算法叫快速傅里叶变换(FFT)(Cooley 与 Tukey 于 1965 年发表,高斯早在 1805 年手稿中便已使用)。这里以最经典的基 2 版本(N=2s)为例。
奇偶拆分#
把 A(x)=a0+a1x+⋯+aN−1xN−1 的偶数下标项和奇数下标项分成两半:
A(x)=(a0+a2x2+a4x4+⋯)+x(a1+a3x2+a5x4+⋯)=E(x2)+xO(x2),
其中 E(z)=∑j=0N/2−1a2jzj 和 O(z)=∑j=0N/2−1a2j+1zj 是两个长度只有 N/2 的多项式。
蝶形运算#
对前半圈 0≤k<N/2,把 x=ωNk 和它对面的 x=ωNk+N/2 同时代入。利用单位根的折半性((ωNk)2=(ωNk+N/2)2=ωN/2k)和对称性(ωNk+N/2=−ωNk),得到:
akak+N/2=E(ωN/2k)+ωNkO(ωN/2k),=E(ωN/2k)−ωNkO(ωN/2k).
记 u=E(ωN/2k)、v=ωNkO(ωN/2k),前后半圈的一对输出直接共享同一次计算:
(ak, ak+N/2)=(u+v, u−v).
这就是蝶形运算。一次长度为 N 的 DFT 拆成两次长度为 N/2 的子 DFT,再加上 N/2 次蝶形合并:
T(N)=2T(N/2)+O(N)⟹T(N)=O(NlogN).
当 N=220≈106 时,N2≈1012,而 2Nlog2N≈107,运算量缩小了五个数量级。以 a=[1,2,0,0] 为例,两层蝶形的真实数值流动如下:
flowchart LR
classDef inp fill:#2f6f8f10,stroke:#2f6f8f
classDef mid fill:#2f6f8f1c,stroke:#2f6f8f,stroke-width:1.4px
classDef out fill:#4f8a4b18,stroke:#4f8a4b,stroke-width:1.5px
subgraph S0["位反转输入"]
I0["a₀ = 1"]:::inp
I2["a₂ = 0"]:::inp
I1["a₁ = 2"]:::inp
I3["a₃ = 0"]:::inp
end
subgraph S1["第 1 层(长度 2 蝶形)"]
E0["E₀ = 1"]:::mid
E1["E₁ = 1"]:::mid
O0["O₀ = 2"]:::mid
O1["O₁ = 2"]:::mid
end
subgraph S2["第 2 层(长度 4 蝶形)"]
Y0["Â₀ = 3"]:::out
Y1["Â₁ = 1 - 2i"]:::out
Y2["Â₂ = -1"]:::out
Y3["Â₃ = 1 + 2i"]:::out
end
I0 -->|"+1"| E0
I2 -->|"+1"| E0
I0 -->|"+1"| E1
I2 -->|"-1"| E1
I1 -->|"+1"| O0
I3 -->|"+1"| O0
I1 -->|"+1"| O1
I3 -->|"-1"| O1
E0 -->|"+u"| Y0
O0 -->|"+ω₄⁰·O₀ = +2"| Y0
E0 -->|"+u"| Y2
O0 -->|"-ω₄⁰·O₀ = -2"| Y2
E1 -->|"+u"| Y1
O1 -->|"+ω₄¹·O₁ = -2i"| Y1
E1 -->|"+u"| Y3
O1 -->|"-ω₄¹·O₁ = +2i"| Y3
mermaid
输入按下标的 3 位二进制反转排列:
0,4,2,6,1,5,3,7
点“下一层”开始合并。每一层都可以点击右侧一列的某个节点,查看算出它的那次蝶形。
- 直接按定义
- 64 次复数乘法
- FFT 已用
- 0 / 12 次蝶形
迭代实现中的位反转#
递归写法很直观,但迭代版 FFT 开头总要做一次“二进制位反转(Bit-Reversal)”重排。以 N=8(三位二进制 000 到 111)为例,把奇偶拆分画成一棵树,原因一眼可见:
flowchart TB
classDef root fill:#2f6f8f18,stroke:#2f6f8f,stroke-width:1.5px
classDef mid fill:#2f6f8f0d,stroke:#2f6f8f
classDef leaf fill:#b0612a14,stroke:#b0612a
R["[0, 1, 2, 3, 4, 5, 6, 7]"]:::root
R -->|"第 1 刀:按最低位 b₀ = 0 / 1"| E["偶 [0, 2, 4, 6]"]:::mid
R --> O["奇 [1, 3, 5, 7]"]:::mid
E -->|"第 2 刀:按中间位 b₁ = 0 / 1"| EE["[0, 4]"]:::mid
E --> EO["[2, 6]"]:::mid
O --> OE["[1, 5]"]:::mid
O --> OO["[3, 7]"]:::mid
EE -->|"第 3 刀:按最高位 b₂"| L0["0 (000)"]:::leaf
EE --> L4["4 (100)"]:::leaf
EO --> L2["2 (010)"]:::leaf
EO --> L6["6 (110)"]:::leaf
OE --> L1["1 (001)"]:::leaf
OE --> L5["5 (101)"]:::leaf
OO --> L3["3 (011)"]:::leaf
OO --> L7["7 (111)"]:::leaf
mermaid
因为递归顶层第一刀切的是二进制的最低位,越早切的一刀越决定元素最终落在左半还是右半(即最终排位的高位)。一路切到底,叶子从左到右的排位恰好就是原下标的倒二进制位。迭代版将数组按位反转摆好之后,后面就能从底往上逐层合并相邻块。
展开查看:长度N=8 的三层蝶形完整计算表
取 a=[1,2,3,4,0,0,0,0](即 A(x)=1+2x+3x2+4x3)。按位反转序 [0,4,2,6,1,5,3,7] 重排后,输入变为 [1, 0, 3, 0, 2, 0, 4, 0]:
| 层 | 旋转因子 | 当前各块结果 |
|---|
| 位反转输入 | — | 1, 0, 3, 0, 2, 0, 4, 0 |
| 第 1 层(块长 2) | ω20=1 | 1,1 ∣ 3,3 ∣ 2,2 ∣ 4,4 |
| 第 2 层(块长 4) | ω40=1, ω41=−i | 4, 1−3i, −2, 1+3i ∣ 6, 2−4i, −2, 2+4i |
| 第 3 层(块长 8) | ω8k=(1−i)k/2k | 见下表 |
第 3 层以左半第 k 项作 u、右半第 k 项乘 ω8k 作 v:
| k | u | v | ak=u+v | ak+4=u−v |
|---|
| 0 | 4 | 6 | 10 | −2 |
| 1 | 1−3i | −2−32i | (1−2)−(3+32)i | (1+2)+(32−3)i |
| 2 | −2 | 2i | −2+2i | −2−2i |
| 3 | 1+3i | 2−32i | (1+2)+(3−32)i | (1−2)+(3+32)i |
三层总共做了 3×4=12 次蝶形,而按 DFT 定义直接算需要 82=64 次复数乘法。
用 FFT 计算多项式乘法#
算一次 (1+2x)(3+4x):
- 补零:结果最多有 2+2−1=3 项,取 N=4,补成 a=[1,2,0,0],b=[3,4,0,0]。
- 正变换:代入 ω4=−i 的幂 (1,−i,−1,i):
a=[3, 1−2i, −1, 1+2i],b=[7, 3−4i, −1, 3+4i].
- 逐点相乘:
c=[21, −5−10i, 1, −5+10i].
- 逆变换:用 ω4−1=+i 求平均:
- c0=41[21+(−5−10i)+1+(−5+10i)]=3;
- c1=41[21+(−5−10i)i−1+(−5+10i)(−i)]=10;
- 同理 c2=8, c3=0。
得到 C(x)=3+10x+8x2,与直接展开完全一致。
NTT#
复数 FFT 的精度边界#
公式里的 cos(2π/N) 和 sin(2π/N) 是精确的,但放进 64 位双精度浮点数(double)后,无理数在第一步就会被截断。经过 log2N 层蝶形运算的舍入累积,原本是整数 3 的系数算出来往往像这样:
2.9999999999997+0.0000000000001i.
只要实部的绝对误差严格小于 0.5,四舍五入就能无损恢复。但随着系数变大、序列变长,误差会迅速逼近这条红线。下面是一组实测(两个长度 1024、非负整数系数在 [0,B) 内的多项式,用标准双精度基 2 FFT 算长度 N=2048 卷积,对照 BigInt 真值):
| 系数上界 B | 乘积最大真实系数 | 实部最大绝对误差 | 四舍五入错误的系数个数 |
|---|
| 103 | 2.69×108 | 7.45×10−8 | 0 |
| 105 | 2.70×1012 | 0.00073 | 0 |
| 106 | 2.70×1014 | 0.09375 | 0 |
| 5×106 | 6.74×1015 | 2.5 | 1206(共 2047 项) |
double 能精确表示的最大连续整数是 253≈9.007×1015,最后一行的真实乘积最大才 6.74×1015,装得进 double但十层蝶形算完后实部误差已经达到 2.5,超过一半的系数取整出错。
有限域里的单位根#
既然误差来自复数单位根里的无理数,不妨回头检查一下:推导 DFT 和基 2 FFT 时,我们到底用到了复数的什么性质?
其实只用了三条纯代数性质:
- 存在一个元素 ω,其 N 次幂为 1,且前 N 次幂互不相同(保证正交求和为 0);
- 支持加、减、乘,且 N 有乘法逆元(保证逆变换能除以 N);
- 当 N 为偶数时,ωN/2=−1 且 ωN2=ωN/2(保证奇偶拆分和蝶形合并)。
只要在一个纯整数的代数世界里找到满足这三条的元素,就能把整套 FFT 代码原样搬过去,全程整数运算、零舍入误差。这个世界就是模素数 p 的有限域 Fp,搬过去后的算法叫数论变换(NTT)。
对任何素数 p,Fp 中非零元素在模 p 乘法下构成阶为 p−1 的循环群,其生成元叫原根 g(g1,…,gp−1modp 跑遍所有非零余数)。只要 N∣(p−1),令:
w=g(p−1)/N(modp),
w 就满足 wN≡1(modp)、wN/2≡−1(modp),并且平方后阶恰好减半,具备单位根的全部代数脾气。
这也是算法竞赛里 998244353 如此常见的原因:
998244353−1=119×223.
它包含足足 23 个因子 2(且原根是 g=3),支持长度最高达 223 的基 2 NTT。相比之下,常用的 109+7 减 1 后只含一个因子 2,连长度 4 的基 2 NTT 都无法运行。
拿 [1,2,3]∗[4,5,6]=[4,13,28,27,18] 做一次长度 N=8 的 NTT。
取 p=17(8∣16,原根 g=3,w=316/8=9(mod17),8−1≡15(mod17)),算完得到:
[4, 13, 11, 10, 1, 0, 0, 0](mod17).
NTT 没有误差,但它只记录模 17 的余数。要让余数直接等于真实非负整数系数,模数 p 必须大于最大真实系数 28 且满足 8∣(p−1)。顺着往后找,第一个满足条件的素数是 p=41(41−1=40=8×5,原根 g=6,w=65≡27(mod41)),换用模 41 算出的就是精确的 [4,13,28,27,18,0,0,0]。
若真实系数超过单个 NTT 素数,可以选两三个互素的 NTT 素数分别计算,再用中国剩余定理(CRT) 拼回大整数(参考 AtCoder Library 的 convolution 说明 ↗)
大致对应关系:
| 概念 | 复数域 FFT | 有限域 NTT |
|---|
| 空间 | C(复数) | Fp(模素数 p 的整数) |
| 单位根 | ω=e2πi/N | w=g(p−1)/Nmodp |
| 逆变换除以 N | 乘以 1/N | 乘以 N−1(modp) |
| ωN/2 | −1 (复数) | p−1 (整数) |
| 误差 | 有浮点舍入误差 | 无误差 |
a=1+2x, b=3+4x,乘积次数为 2,需要 3 个系数,取
N=4 并补零
- 补零
- 变换 a
- 变换 b
- 逐点相乘
- 逆变换
- 读出结果
| k | ak | bk | a^k | b^k | c^k=a^kb^k | 逆变换的实部 | 取整 |
| 0 | 1 | 3 | · | · | · | · | · |
|---|
| 1 | 2 | 4 | · | · | · | · | · |
|---|
| 2 | 0 | 0 | · | · | · | · | · |
|---|
| 3 | 0 | 0 | · | · | · | · | · |
每一步都在表里新增一列。灰色的列还没有算到。
本面板实际调用与蝶形实验相同的基 2 FFT;逆变换使用共轭、正变换和除以 N。它展示的是这组输入的计算结果,不能作为所有 FFT 实现的误差界。
延伸阅读#
2026 年 10 月 6 日,OpenAI 发布了一大坨数学成果,不乏各种领域的硕大果实,其中在计算机科学领域,矩阵乘法复杂度上界降至 ω(C)≤2.25 的突破 大概最为亮眼,在这里边就有涉及到了 FFT 相关内容。
本来这个文章是为了讲矩阵乘法的突破的,不过奈何感觉很难以科普的口吻讲出来,所以做了巨量删减。由于要处理事情还蛮多的,对于这个部分的内容就先暂缓吧。 对于矩阵复杂度突破历史推荐看矩阵乘法的复杂度能达到多低? ↗

