FXJ Wiki

Back

输入序列、卷积响应与频谱的示意输入序列、卷积响应与频谱的示意

大致结构:本篇文章主要讲解 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

约定:文中的离散序列默认从下标 00 开始,未写出的项视为 00;离散傅里叶变换(DFT)使用负指数作为正变换,正指数并除以 NN 作为逆变换(不同教材正负号可能对调,只要正逆配对即可)。

你可以按四幕顺序通读,前三幕构成卷积与 FFT,第四幕延伸至矩阵乘法与前沿研究:

  1. 第一幕:从 音乐厅的余音 走到 多项式乘法,看清 O(N2)O(N^2) 交叉项的来源。
  2. 第二幕:经由 点值表示、复数、欧拉公式 与 单位根,理解 傅里叶变换 与 DFT。
  3. 第三幕:理清 循环卷积与补零、FFT 蝶形与位反转,以及模数世界里的 NTT。
  4. 第四幕:从 循环矩阵对角化 切入 Karatsuba 与 Strassen、张量秩与边界秩,最后读懂 9/4 论文的核心构造。

卷积的理解#

在音乐厅里,一个音结束了,它留下的影响却未必结束。

新的琴声不断响起,旧的琴声还在墙壁和穹顶之间来回反射。听众此刻听到的,是过去所有声音经过音乐厅改造后、在当前时刻叠在一起的结果。

卷积描述的正是这个过程:每一次输入都在时间里拖出一条尾巴,所有尾巴在当前时刻相遇,叠成此刻的输出。

现在我们请出三个角色:演奏家、音乐厅、听众。

一个音与它的余音#

在音乐厅里轻轻敲一下琴键,声音响起,随后渐渐消散。

我们先做一个理想化的简化:把这次按键当成瞬间发生、强度为 11 的“标准一下”。 按键本身短促得像个点,但音乐厅不会立刻安静下来——把音乐厅对这“标准一下”的响应曲线记作 h(t)h(t),其中 tt 表示从按键那一刻算起,已经过去了多久。

同样敲一下,放进浴室、空教室、大音乐厅,拖出来的尾巴 h(t)h(t) 各不相同。

当然,前提是这间音乐厅守两条规矩:

  • 时不变:同样一下琴声,晚 3 秒敲,余音也只是原封不动地晚 3 秒出现,不会因为过了中午就变调。
  • 线性:按键力度放大 aa 倍,余音也按比例放大 aa 倍;先后敲两下琴键,厅里的声音就是两段余音直接相加。

满足这两条规矩的系统,叫线性时不变系统(LTI)。

Single impulse response h(t) and linear superposition of shifted, scaled responses. Single impulse response h(t) and linear superposition of shifted, scaled responses.
左:单位冲激输入对应的响应曲线 h(t);右:多次按不同力度和时刻触发的余音按线性时不变规则平移、缩放并叠加。

为什么要翻转#

刚学卷积时,我们大概会被课本上“先把 h(τ)h(\tau) 翻转成 h(−τ)h(-\tau),再平移成 h(t−τ)h(t-\tau)”绕晕:好端端的声音传播,怎么还带倒着走的?

声音并没有倒着走,只是我们从演奏家的琴凳,换到了听众席的座位上。

先坐到演奏家的位置上。假设整首曲子由一串短促的按键组成,第 kk 次按键发生在 τk\tau_k 时刻,力度是 aka_k。到了后来的 tt 时刻,这次按键已经过去了 t−τkt-\tau_k 这么久,它在厅里留下的余音自然是:

ak h(t−τk).a_k\, h(t-\tau_k).

把所有按键拖出来的余音叠在一起,就是听众在 tt 时刻听到的总声音:

y(t)=∑kak h(t−τk).y(t) = \sum_{k} a_k\, h(t-\tau_k).

现在换到听众席。听众不关心某个音未来去哪儿,只关心此时此刻 tt,我耳朵里听到的声音是从过去哪些时刻凑出来的?

固定住现在的时刻 tt,沿着输入时间轴 τ\tau 往回盘点:

  • 越是刚刚敲响的音(τ\tau 越靠右、越贴近 tt),它在空气里飘的时间 t−τt-\tau 越短,要查响应说明书 hh 靠左的开头部分;
  • 越是老早以前敲响的音(τ\tau 越靠左、离 tt 越远),它飘的时间 t−τt-\tau 反而越长,要查 hh 靠右的尾巴部分。

输入时刻 τ\tau 往右走,经过的时间 t−τt-\tau 在往左缩。

所以,当我们把响应曲线画在“输入时刻 τ\tau”这条横轴上时,曲线的朝向自然就掉了个头:

h(τ)→掉头往回看h(−τ)→站在时刻 t 盘点h(t−τ).h(\tau) \xrightarrow{\text{掉头往回看}} h(-\tau) \xrightarrow{\text{站在时刻 }t\text{ 盘点}} h(t-\tau).
Flipping and shifting h(tau) to h(t - tau) when viewing past inputs from time t. Flipping and shifting h(tau) to h(t - tau) when viewing past inputs from time t.
站在听众时刻 t 回头沿输入轴 τ 盘点:τ 越靠近 t,经过的时间 t - τ 越短,因此响应曲线在 τ 轴上呈现为翻转并平移后的 h(t - τ)。

所谓“翻转、平移”,并非物理世界里有什么东西倒转了,即站在当前时刻 tt 回头清点时,离现在越近的输入,对应持续作用的时间越短。

连续声音#

如果演奏的不是顿音,而是一段连绵不断的小提琴声 x(t)x(t) 呢?

办法依然朴素:把时间轴切成许多宽度为 Δτ\Delta\tau 的小薄片。只要切得够薄,τk\tau_k 附近那一小片的声音强度几乎不变,整片的“份额”就是高度乘宽度 x(τk)Δτx(\tau_k)\Delta\tau。

Slicing continuous input x(tau) into strips of width d(tau) to form the convolution integral. Slicing continuous input x(tau) into strips of width d(tau) to form the convolution integral.
把连续输入 x(τ) 切成宽度为 dτ 的薄片,每一薄片视作权重为 x(τ)dτ 的瞬时冲激,各自拖出按比例缩放的余音并积分叠加。

把这一小片当成一次权重为 x(τk)Δτx(\tau_k)\Delta\tau 的瞬间敲击,它在 tt 时刻留下的贡献就是 x(τk)h(t−τk)Δτx(\tau_k)h(t-\tau_k)\Delta\tau。把所有时间薄片的贡献加起来,再让薄片宽度 Δτ→0\Delta\tau \to 0,求和号就变成了积分号:

y(t)=(x∗h)(t)=∫−∞+∞x(τ) h(t−τ) dτ.\boxed{y(t) = (x*h)(t) = \int_{-\infty}^{+\infty} x(\tau)\,h(t-\tau)\,d\tau.}

在真实的音乐厅里,未来的声音还没发出,不会影响现在(即当 τ>t\tau > t 时 h(t−τ)=0h(t-\tau)=0,称为因果性),所以积分上限写到 tt 就够了。

展开查看:用单位冲激δ(t)\delta(t) 写出的四步推导

如果用广义函数里的狄拉克 δ\delta 函数(宽度压到 00、高度撑到无穷、但面积恒为 11 的理想尖峰),任何连续信号 x(t)x(t) 都可以写成无数个尖峰的加权叠加(筛选性质):

x(t)=∫−∞+∞x(τ) δ(t−τ) dτ.x(t) = \int_{-\infty}^{+\infty} x(\tau)\,\delta(t-\tau)\,d\tau.

把它送进线性时不变系统,只需四步就能直接写出卷积公式:

  1. 标准一下的定义:δ(t)⟼h(t)\delta(t) \longmapsto h(t)
  2. 时不变(推迟 τ\tau):δ(t−τ)⟼h(t−τ)\delta(t-\tau) \longmapsto h(t-\tau)
  3. 线性缩放(乘常数 x(τ)x(\tau)):x(τ)δ(t−τ)⟼x(τ)h(t−τ)x(\tau)\delta(t-\tau) \longmapsto x(\tau)h(t-\tau)
  4. 线性叠加(对所有 τ\tau 积分):∫x(τ)δ(t−τ) dτ⟼∫x(τ)h(t−τ) dτ=y(t)\int x(\tau)\delta(t-\tau)\,d\tau \longmapsto \int x(\tau)h(t-\tau)\,d\tau = y(t)。

(注:在数学上把系统算子搬进积分号内部,需要信号与响应满足适当的连续性或可积性条件,例如 x,h∈L1(R)x,h \in L^1(\mathbb R);更完整的背景可参考 MIT 6.003 课程讲义 ↗,本节音乐厅的叙事灵感参考自 B 站上的这期卷积漫谈视频 ↗。)

例子#

把连续时间换成离散的格子,就会更易理解了。

假设一个极简音乐厅:敲一下强度为 11 的音,当前这一格响 11,下一格留 0.50.5 的余音,再往后归零,即 h=[1,0.5]h = [1, 0.5]。

我们在第 00 格和第 11 格连续敲两下,力度分别是 22 和 33(x=[2,3]x = [2, 3]):

  • 第 00 格:只有第一次按键刚响起,输出 2×1=22\times 1 = 2;
  • 第 11 格:第一次按键留下的余音 2×0.5=12\times 0.5 = 1,撞上第二次按键的新声音 3×1=33\times 1 = 3,叠出 44;
  • 第 22 格:只剩第二次按键的余音 3×0.5=1.53\times 0.5 = 1.5。
[2, 3]∗[1, 0.5]=[2, 4, 1.5].[2,\ 3] * [1,\ 0.5] = [2,\ 4,\ 1.5].

中间那个 44 即新的到了,旧的还在。

按下标之和配对的理解#

把刚才的手算写成通用的离散序列公式。设输入序列为 aa,系统响应为 bb,输出序列的第 kk 项是:

ck=(a∗b)k=∑j∈Zaj bk−j.c_k = (a*b)_k = \sum_{j\in\mathbb Z} a_j\, b_{k-j}.

盯住 aja_j 和 bk−jb_{k-j} 脚底下的两个下标看一眼:

j+(k−j)=k.j + (k - j) = k.

换句话说,离散卷积做的唯一一件事,就是把所有“下标加起来等于 kk”的成对乘积 aibja_i b_j 统统收进同一个篮子里,加起来交给 ckc_k。

ck=∑i+j=kai bj.\boxed{c_k = \sum_{i+j=k} a_i\, b_j.}

例子#

取 a=[1,2,3]a=[1,2,3],b=[4,5,6]b=[4,5,6]。按“下标之和等于 kk”分拣全部 3×3=93\times 3 = 9 个乘积:

c0=a0b0=1⋅4=4,c1=a0b1+a1b0=1⋅5+2⋅4=13,c2=a0b2+a1b1+a2b0=1⋅6+2⋅5+3⋅4=28,c3=a1b2+a2b1=2⋅6+3⋅5=27,c4=a2b2=3⋅6=18.\begin{aligned} c_0 &= a_0b_0 = 1\cdot 4 = 4, \\ c_1 &= a_0b_1 + a_1b_0 = 1\cdot 5 + 2\cdot 4 = 13, \\ c_2 &= a_0b_2 + a_1b_1 + a_2b_0 = 1\cdot 6 + 2\cdot 5 + 3\cdot 4 = 28, \\ c_3 &= a_1b_2 + a_2b_1 = 2\cdot 6 + 3\cdot 5 = 27, \\ c_4 &= a_2b_2 = 3\cdot 6 = 18. \end{aligned}

所以 [1,2,3]∗[4,5,6]=[4,13,28,27,18][1,2,3]*[4,5,6] = [4,13,28,27,18]。

交互实验 · 卷积 在实验室中打开 →

此刻听到的,是过去每一刻留下的余音

卷积参数
离散预设
a 的长度 b 的长度
c2=∑i+j=2aibj=a0b2+a1b1+a2b0=1⋅6+2⋅5+3⋅4=28c_{2}=\sum_{i+j=2}a_ib_j=a_{0}b_{2}+a_{1}b_{1}+a_{2}b_{0}=1\cdot6+2\cdot5+3\cdot4=28
第 0 拍 (a₀=1)余音衰减 →6第 1 拍 (a₁=2)余音衰减 →10第 2 拍 (a₂=3)余音衰减 →12听众听到的总声各拍余音叠加4t=013t=128t=227t=318t=4听众此刻 t=2:总音量 28
1a02a13a2输入 a:每一下的强度
4b05b16b2响应 b:一下之后每格的余音
列 j:余音 b45614562810123121518行 i
4c013c128c227c318c4

柱子按来源分色:颜色 i 是第 i 个输入拖出的余音。选中列的色块,就是左边表里高亮的那条斜线。

A(x)B(x)=(1+2x+3x2)(4+5x+6x2)=4+13x+28x2+27x3+18x4A(x)B(x)=(1+2x+3x^{2})(4+5x+6x^{2})=4+13x+28x^{2}+27x^{3}+18x^{4}

普通卷积的长度是 3+3−1=5。把下面的 N 拉到 5 或更大,循环卷积就和它完全一样;小于 5 时,末尾的项会绕回开头。

注意结果的长度:两个长度分别为 nn 和 mm 的序列,最大下标是 n−1n-1 和 m−1m-1,加起来最远走到 n+m−2n+m-2。从 00 数到 n+m−2n+m-2,一共会有 n+m−1n+m-1 个篮子(这个数字后面做补零时会反复用到)。

按下标之和装篮的结构在概率论里也很常见:掷两颗独立的六面骰子,aia_i 和 bjb_j 是各自掷出 i,ji,j 点的概率,那么“点数之和等于 kk”的总概率就是把所有 i+j=ki+j=k 的联合概率 aibja_i b_j 加起来——独立随机变量之和的分布,天然就是它们各自概率分布的卷积。

多项式与卷积#

现在回答开篇的第一个问题:音乐厅里的余音,怎么会跟多项式乘法撞在一起?

刚才我们已经看清,卷积的核心动作是:只要 i+j=ki+j=k,就把 aibja_i b_j 归入第 kk 号篮子。而在初中学过的代数运算里,天生满足“相乘时脚标自动相加”的,正是指数运算:xi⋅xj=xi+jx^i \cdot x^j = x^{i+j}。

给序列 a=[a0,a1,…,an−1]a=[a_0,a_1,\ldots,a_{n-1}] 的每一项贴上一张写着 xix^i 的标签,拼成多项式:

A(x)=a0+a1x+a2x2+⋯+an−1xn−1,A(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1},

同样把 bb 写成 B(x)=∑jbjxjB(x) = \sum_j b_j x^j。按分配律乘开、合并同类项:

A(x)B(x)=(∑iaixi)(∑jbjxj)=∑k(∑i+j=kaibj)xk.A(x)B(x) = \left(\sum_i a_i x^i\right)\left(\sum_j b_j x^j\right) = \sum_k \left(\sum_{i+j=k} a_i b_j\right) x^k.

xkx^k 前面的系数就是离散卷积 ckc_k:

(1+2x+3x2)(4+5x+6x2)=4+13x+28x2+27x3+18x4.(1+2x+3x^2)(4+5x+6x^2) = 4 + 13x + 28x^2 + 27x^3 + 18x^4.

在这里不必把 xx 当成急着代数字求值的“未知数”。在生成函数眼里,xx 更像一个占位符:xix^i 负责记住 aia_i 原来坐在第 ii 号位置,并在相乘时靠指数加法 xixj=xi+jx^i x^j = x^{i+j} 自动把乘积送进第 i+ji+j 号位置。

交叉项带来的瓶颈#

不管叫离散卷积还是多项式乘法,只要按定义直接算,每个 aia_i 都得和每个 bjb_j 相乘一次。两个长度为 NN 的序列卷在一起,总共要做 N2N^2 次乘法。

当 N=105N=10^5 时,N2=1010N^2 = 10^{10},直接算显然吃不消。于是核心问题浮出水面:

输出一共只有 2N−12N-1 项,我们真的必须把中间那 N2N^2 个交叉乘积 aibja_i b_j 逐个算出来吗?能不能换个坐标系,让两边“各乘各的”?

点值表示的诱惑与困境#

想避开“项与项两两交叉”,代数里早就有一条捷径:点值表示。

一条抛物线 C(x)=c0+c1x+c2x2C(x) = c_0 + c_1 x + c_2 x^2,可以用三个系数 (c0,c1,c2)(c_0, c_1, c_2) 描述,也可以在横轴上任取 3 个不同的点(比如 x=0,1,2x=0, 1, 2),用它的三个高度 (C(0),C(1),C(2))(C(0), C(1), C(2)) 描述。

一般地,一个次数小于 NN 的多项式,由它在 NN 个互不相同的点 x0,x1,…,xN−1x_0, x_1, \ldots, x_{N-1} 上的取值唯一确定(因为两个次数小于 NN 的不同多项式相减,最多只能有 N−1N-1 个根,不可能在 NN 个点上全相等)。

一旦换到点值表示,原本 O(N2)O(N^2) 的交叉相乘变成了 O(N)O(N) 的逐点相乘:

C(xk)=A(xk)⋅B(xk),k=0,1,…,N−1.C(x_k) = A(x_k)\cdot B(x_k), \qquad k = 0, 1, \ldots, N-1.

在第 kk 个点上,A(xk)A(x_k) 只跟 B(xk)B(x_k) 相乘,与其他点完全无关——交叉项消失了。

换坐标系的代价#

既然这么省事,为什么不随便挑 x=0,1,2,…,N−1x = 0, 1, 2, \ldots, 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^)FaC_b a = F^{-1}\operatorname{diag}(\widehat b) F a 严丝合缝地重合。)

如果随便挑 NN 个点,把一个 NN 项多项式代进 1 个点要算 O(N)O(N) 次,代进 NN 个点就要 O(N2)O(N^2) 次;算完再插值回系数(解范德蒙德方程组)直接算又是 O(N2)O(N^2),而且实数等距点的幂次 2N,3N2^N, 3^N 增长极快,会把范德蒙德矩阵的条件数推向指数级恶化,稍微有点浮点舍入就会让插值严重失真。

交互实验 · 点值表示 在实验室中打开 →

同一个多项式的两种描述:系数和点值

点值表示参数
nn
3 个点值确定次数 <3 的多项式:插值得到 3+10x+8x2=C(x)3\text{ 个点值确定次数 }<3\text{ 的多项式:插值得到 }3+10x+8x^{2}=C(x)
−404812−2−1.5−1−0.500.5

A=1+2xB=3+4xC=AB

xjx_jA(xj)A(x_j)B(xj)B(x_j)A(xj)B(xj)A(x_j)B(x_j)
−1.5−2−36
−0.5010
0.52510

点值表示下,乘法只是把同一行的两个数相乘,3 个点就做 3 次乘法。C 的次数是 2,3 个点已经够用;多出来的点只是重复确认同一个多项式。

插值有多稳:范德蒙德矩阵的条件数 κ2(V)\kappa_2(V)

点数 n本图的实数点xj=0,1,…,n−1x_j=0,1,\ldots,n-1单位根
21.62.61
35.613.91
421.91541
64245.77×10⁴1
895395.29×10⁷1
126.00×10⁶2.46×10¹⁴1
164.37×10⁹>10¹⁵1

从点值解出系数,就是解方程 Vc=yV\mathbf c=\mathbf y,其中 Vjp=xj pV_{jp}=x_j^{\,p}。固定精确的 V、仅扰动右端点值时,系数向量在 2 范数下的相对误差至多是点值相对误差的 κ2(V)\kappa_2(V) 倍。这里的条件数描述最坏方向的敏感性,不表示每组数据都会损失对应位数,也不保证每个系数的相对误差。

单位根的 V 是傅里叶矩阵 F,满足 F∗F=N IF^*F=N\,I,因此 F/NF/\sqrt N 是酉矩阵且 κ2(F)=1\kappa_2(F)=1:上述范数相对误差不会因这个线性问题被放大。计算单位根、执行变换与逐点乘法仍有浮点舍入误差;大条件数的表值本身也只是双精度估计。现在的 3 个实数点,估计条件数为 5.6。

现在等于原地踏步… 所以真正的问题变成:

能不能挑一组特殊的采样点 x0,…,xN−1x_0, \ldots, x_{N-1},让它们之间存在对称关系——算出前一半点的值,后一半就能顺手复用?

把多项式按偶数次项和奇数次项拆开,就能看出我们需要什么样的点:

A(x)=(a0+a2x2+a4x4+⋯ )+x(a1+a3x2+a5x4+⋯ )=E(x2)+xO(x2).A(x) = (a_0 + a_2 x^2 + a_4 x^4 + \cdots) + x(a_1 + a_3 x^2 + a_5 x^4 + \cdots) = E(x^2) + x O(x^2).

右边的 E(⋅)E(\cdot) 和 O(⋅)O(\cdot) 吃的都是 x2x^2。只要我们挑的 NN 个点两两互为相反数 (x,−x)(x, -x),平方之后 NN 个点就会坍缩成 N/2N/2 个不同的平方值 x2x^2,问题规模减半。

可是在实数轴上,这招只能用一次:第一次挑 ±1,±2,±3,±4\pm 1, \pm 2, \pm 3, \pm 4,平方之后变成 1,4,9,161, 4, 9, 16——全是正数。下一层还想找互为相反数的点,就得要求某个数满足 z2=−正数z^2 = -\text{正数}。

实数轴太窄了,一下子就撞上了平方非负的墙。 要想一路对半折上 log⁡2N\log_2 N 次,我们只能走出实数轴,去请出平方等于 −1-1 的数。

复数#

乘以 i 的意义#

方程 x2=−1x^2 = -1 在实数轴上无解。引入虚数单位 ii,规定

i2=−1,i^2 = -1,

再把所有形如 z=a+biz = a + bi(a,b∈Ra,b\in\mathbb R)的数合称复数,画在二维平面上的点 (a,b)(a,b)。它的模长是 ∣z∣=a2+b2|z| = \sqrt{a^2+b^2},共轭是 z‾=a−bi\overline z = a - bi,两者相乘消掉虚部:zz‾=a2+b2=∣z∣2z\overline z = a^2 + b^2 = |z|^2。

但如果只把 ii 当成一个死记硬背的符号,就错过了复数最漂亮的地方。算一下把平面上的点 (a,b)(a,b) 乘上 ii 会怎样:

i(a+bi)=−b+ai.i(a + bi) = -b + ai.

原来的向量 (a,b)(a,b) 变成了 (−b,a)(-b,a):长度不变,方向刚好逆时针转了 90∘90^\circ。

1→×ii→×i−1→×i−i→×i1.1 \xrightarrow{\times i} i \xrightarrow{\times i} -1 \xrightarrow{\times i} -i \xrightarrow{\times i} 1.

这样看,i2=−1i^2 = -1 就非常自然了:乘一次 ii 是逆时针转 90∘90^\circ,连乘两次转 180∘180^\circ,自然掉头指向反方向的 −1-1。

长度相乘,角度相加#

把任意两个复数写成极坐标(模长 r,sr, s、夹角 θ,ϕ\theta, \phi):

z=r(cos⁡θ+isin⁡θ),w=s(cos⁡ϕ+isin⁡ϕ).z = r(\cos\theta + i\sin\theta), \qquad w = s(\cos\phi + i\sin\phi).

直接乘开,套用三角函数的和角公式:

zw=rs[(cos⁡θcos⁡ϕ−sin⁡θsin⁡ϕ)+i(sin⁡θcos⁡ϕ+cos⁡θsin⁡ϕ)]=rs(cos⁡(θ+ϕ)+isin⁡(θ+ϕ)).\begin{aligned} zw &= rs\bigl[(\cos\theta\cos\phi - \sin\theta\sin\phi) + i(\sin\theta\cos\phi + \cos\theta\sin\phi)\bigr] \\ &= rs\bigl(\cos(\theta+\phi) + i\sin(\theta+\phi)\bigr). \end{aligned}

复数乘法的几何本质就八个字:模长相乘,角度相加。 特别是当你乘上一个模长 r=1r=1(落在单位圆上)的复数时,它不改变原向量的长度,是一个纯粹的旋转算子。

Complex multiplication scales lengths and adds angles; multiplying by i rotates by 90 degrees. Complex multiplication scales lengths and adds angles; multiplying by i rotates by 90 degrees.
左:乘以 i 等价于逆时针旋转 90°;右:一般复数相乘将模长相乘、辐角相加。

交互实验 · 复数乘法 在实验室中打开 →

乘一个复数,就是把整个平面转一下、放缩一下

复数乘法参数
把 w 设为
∣z∣ ∣w∣=1.58×1.17=1.84=∣zw∣,arg⁡z+arg⁡w=18.4∘+59∘≡77.5∘|z|\,|w|=1.58\times1.17=1.84=|zw|,\quad \arg z+\arg w=18.4^\circ+59^\circ\equiv77.5^\circ
1izwzw

z=1.5+0.5iz=1.5+0.5i

w=0.6+iw=0.6+i

zw=0.4+1.8izw=0.4+1.8i

淡色的单位方格和字母 F 是原图;实线是它们乘以 z 之后的样子。整个平面被同一个复数旋转并缩放,方格依旧是方格:乘法不会把平面拉歪。

欧拉公式#

每次写 cos⁡θ+isin⁡θ\cos\theta + i\sin\theta 还是偏啰嗦。既然“两个单位复数相乘,等于把它们的角度 θ\theta 和 ϕ\phi 相加”,而在基础数学里,天生满足“函数值相乘 = 自变量相加”的,又是指数函数 eA⋅eB=eA+Be^A \cdot e^B = e^{A+B}。

把复指数 eiθe^{i\theta} 代进实数指数函数的泰勒幂级数 ez=∑n=0∞znn!e^z = \sum_{n=0}^{\infty} \frac{z^n}{n!},按偶数项和奇数项分组(利用 i2=−1,i3=−i,i4=1i^2=-1, i^3=-i, i^4=1 每四步一循环):

eiθ=(1−θ22!+θ44!−⋯ )+i(θ−θ33!+θ55!−⋯ )=cos⁡θ+isin⁡θ.\begin{aligned} e^{i\theta} &= \left(1 - \frac{\theta^2}{2!} + \frac{\theta^4}{4!} - \cdots\right) + i\left(\theta - \frac{\theta^3}{3!} + \frac{\theta^5}{5!} - \cdots\right) \\ &= \cos\theta + i\sin\theta. \end{aligned}

这就是欧拉公式(MIT 18.03 复数与指数讲义 ↗给出了更多几何视角)。

大家平时常感叹它的特例 eiπ+1=0e^{i\pi} + 1 = 0,但在算法与信号处理里,它真正的威力在于:它把平面上的旋转角度 θ\theta 直接放进了指数的肩膀上。

  • ∣eiθ∣=cos⁡2θ+sin⁡2θ=1|e^{i\theta}| = \sqrt{\cos^2\theta + \sin^2\theta} = 1:只要指数是纯虚数 iθi\theta,它就待在单位圆上,角度为 θ\theta;
  • eiαeiβ=ei(α+β)e^{i\alpha} e^{i\beta} = e^{i(\alpha+\beta)}
  • 把 eiθe^{i\theta} 和共轭 e−iθe^{-i\theta} 相加相减:
cos⁡θ=eiθ+e−iθ2,sin⁡θ=eiθ−e−iθ2i.\cos\theta = \frac{e^{i\theta} + e^{-i\theta}}{2}, \qquad \sin\theta = \frac{e^{i\theta} - e^{-i\theta}}{2i}.

交互实验 · 欧拉公式 在实验室中打开 →

指数级数为什么会绕成一个圆

欧拉公式参数
θ=π,∑n=05(iθ)nn!=0.124+0.524i,∣误差∣=1.2401\theta=\pi,\quad \sum_{n=0}^{5}\frac{(i\theta)^n}{n!}=0.124+0.524i,\quad |\text{误差}|=1.2401
eiθ
  1. (iθ)00!\frac{(i\theta)^{0}}{0!}实方向 +1,长 1
  2. (iθ)11!\frac{(i\theta)^{1}}{1!}虚方向 +i,长 3.142
  3. (iθ)22!\frac{(i\theta)^{2}}{2!}实方向 −1,长 4.935
  4. (iθ)33!\frac{(i\theta)^{3}}{3!}虚方向 −i,长 5.168
  5. (iθ)44!\frac{(i\theta)^{4}}{4!}实方向 +1,长 4.059
  6. (iθ)55!\frac{(i\theta)^{5}}{5!}虚方向 +i,长 2.55

每一项都是上一项乘以 iθn+1\tfrac{i\theta}{n+1}:先转 90°,再按 θn+1\tfrac{\theta}{n+1} 缩放。本实验取 θ≥0,非零项依次向左转;随着项数充分增加,部分和趋向单位圆上角度为 θ 的点。项数有限时,终点可能仍离它很远。实部方向的项(偶数项)拼出 cos θ,虚部方向的项(奇数项)拼出 sin θ。

10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110¹0510152025n

柱高是第 n 项的长度 θn/n!\theta^n/n!(对数刻度,10−610^{-6} 以下截平),蓝色是已经加上的项。相邻两项之比是 θ/(n+1)\theta/(n+1):比值大于 1 时项还在变长,小于 1 后开始缩短。橙色标出最长项之一,第 3 项,长 5.17;画出的 30 项部分和离原点最远时是 5.04。

上方误差比较的是当前有限项和与 sin、cos 算出的目标,包含级数截断与浮点舍入两种影响。较大的中间数相消会增加舍入风险,但最长项不能直接给出误差或可信位数。本实验最多相加 30 项,θ 较大时截断误差仍可能很大;继续增加项数与控制浮点误差是两个问题。

单位根*#

铺垫完复数和欧拉公式,现在回到“点值表示”结尾的死结:去哪儿找 NN 个点,能让它们平方之后数量减半、还能一路对半折下去?

答案在单位圆上。方程

zN=1z^N = 1

要找的是连着自乘 NN 次(角度连翻 NN 倍)后刚好转回 11 的复数。把一整圈 2π2\pi 平均切成 NN 份,记顺时针转一份的基本步长为:

ωN=e−2πi/N,\omega_N = e^{-2\pi i / N},

那么它的 0,1,…,N−10, 1, \ldots, N-1 次幂:

ωN0, ωN1, ωN2, …, ωNN−1\omega_N^0,\ \omega_N^1,\ \omega_N^2,\ \ldots,\ \omega_N^{N-1}

像切披萨一样把单位圆均匀分成 NN 个点,叫作 NN 次单位根(其中 ωN\omega_N 走满 NN 步才第一次回到 11,叫本原 NN 次单位根)。

当 NN 是偶数时,这组点同时满足三条极好用的性质:

  1. 周期性:ωNk+N=ωNk\omega_N^{k+N} = \omega_N^k。
  2. 对称性:ωNk+N/2=ωNk⋅e−πi=−ωNk\omega_N^{k+N/2} = \omega_N^k \cdot e^{-\pi i} = -\omega_N^k。相隔半圈的两个点,天然互为相反数。
  3. 折半性:平方之后,自动落到半圈规模的单位根上:
(ωNk)2=(ωN2)k=(e−2πi/(N/2))k=ωN/2k.(\omega_N^k)^2 = (\omega_N^2)^k = \left(e^{-2\pi i / (N/2)}\right)^k = \omega_{N/2}^k.

拿 N=4N=4 试一下:ω4=−i\omega_4 = -i,四个 4 次单位根是 (1,−i,−1,i)(1, -i, -1, i)。全部平方后变成 (1,−1,1,−1)(1, -1, 1, -1)——只剩 (1,−1)(1, -1) 两个 2 次单位根;再平方一次,只剩 11 这个 1 次单位根。把 N=8N=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=2sN=2^s 有多大,都能一路平方、一路对半折到底。而且它们模长恒为 11、彼此正交,构成的傅里叶矩阵 2-范数条件数恒为 11,也顺手避开了实数等距点插值时的数值失控。

单位根的正交求和#

单位根还有一条贯穿后文(DFT 逆变换乃至 9/4 论文)。任取整数 rr:

∑j=0N−1ωNjr={N,若 N∣r,0,若 N∤r.\sum_{j=0}^{N-1} \omega_N^{jr} = \begin{cases} N, & \text{若 } N \mid r, \\ 0, & \text{若 } N \nmid r. \end{cases}

证明:

  • 若 N∣rN \mid r,每一项都是 ωNr=1\omega_N^r = 1,NN 个 11 相加得 NN;
  • 若 N∤rN \nmid r,公比 q=ωNr≠1q = \omega_N^r \ne 1 且 qN=1q^N = 1,等比数列求和 1−qN1−q=0\frac{1-q^N}{1-q} = 0。

直觉:当 N∤rN \nmid r 时,这 NN 个单位向量在圆周上均匀分布,像 NN 个人围成一圈朝四面八方拉绳子,合力严格抵消为 00;只有大家朝同一个方向(N∣rN \mid r)使劲时,合力才会累加出 NN。 「合拍得 NN、不合拍归 00」

8th roots of unity on the unit circle and head-to-tail geometric proof of orthogonality. 8th roots of unity on the unit circle and head-to-tail geometric proof of orthogonality.
左:8 次单位根均匀分布在单位圆上,关于原点对称的点互为相反数;右:非平凡步长下,8 个单位向量首尾相接围成闭合正多边形,总和严格为 0。

交互实验 · 单位根 在实验室中打开 →

转完整数圈,箭头首尾相接回到起点

单位根参数
8∤1:∑j=07ωj=1−ω81−ω=1−11−ω=08\nmid 1\text{:}\sum_{j=0}^{7}\omega^{j}=\frac{1-\omega^{8}}{1-\omega}=\frac{1-1}{1-\omega}=0
ω⁰ω¹ω²ω³ω⁴ω⁵ω⁶ω⁷每步乘 ω^1,跳 1 格
起点把 ω^(1j) 首尾相接,j = 0…7

ω1=0.71−0.71i\omega^{1}=0.71-0.71i。ω^1 是转 1/8 圈的旋转。走 8 步回到起点,折线是一个正 8 边形;闭合的折线首尾重合,和为 0。 虚线连着 ω⁰ 和 ω^4:ω4=−1\omega^{4}=-1,相对的两个根互为相反数,FFT 正是靠这一点把计算对半分。

同一个和,拼成矩阵:F F∗=N IF\,F^{*}=N\,I

00800000001108000000220080000033000800004400008000550000080066000000807700000008

傅里叶矩阵 Fjm=ωjmF_{jm}=\omega^{jm}。FF∗F F^{*} 的第 (j,k)(j,k) 格是 ∑mωjm ωkm‾=∑mω(j−k)m\sum_{m}\omega^{jm}\,\overline{\omega^{km}}=\sum_{m}\omega^{(j-k)m},正好是右上图 r=j−kr=j-k 时的和:只有对角线上 j=kj=k 时为 8,其余都是 0。高亮的是 j−k≡1(mod8)j-k\equiv1\pmod{8} 的那条斜线,点任意一格可以换成那一格的 r。于是 F−1=1NF∗F^{-1}=\tfrac{1}{N}F^{*}:逆变换只要把 ω 换成 ω−1\omega^{-1},再除以 N,不需要另解方程。

复指数:卷积的特征函数#

在进入离散算法之前,回看一下连续信号:为什么信号处理总是围绕 e2πifte^{2\pi i f t} 打转?

把频率为 ff 的纯旋转信号 x(t)=e2πiftx(t) = e^{2\pi i f t} 送进冲激响应为 h(τ)h(\tau) 的音乐厅里,计算输出 y(t)y(t):

y(t)=∫−∞∞h(τ) x(t−τ) dτ=∫−∞∞h(τ) e2πif(t−τ) dτ=(∫−∞∞h(τ) e−2πifτ dτ)⏟H(f)⋅e2πift=H(f) e2πift.\begin{aligned} y(t) &= \int_{-\infty}^{\infty} h(\tau)\, x(t-\tau)\, d\tau \\ &= \int_{-\infty}^{\infty} h(\tau)\, e^{2\pi i f (t-\tau)}\, d\tau \\ &= \underbrace{\left(\int_{-\infty}^{\infty} h(\tau)\, e^{-2\pi i f \tau}\, d\tau\right)}_{H(f)} \cdot e^{2\pi i f t} = H(f)\, e^{2\pi i f t}. \end{aligned}

能把 e2πif(t−τ)e^{2\pi i f(t-\tau)} 拆成 e2πift⋅e−2πifτe^{2\pi i f t}\cdot e^{-2\pi i f \tau} 并提出积分号外,靠的依然是指数把时间加减变成了乘法。而结果非常耐人寻味:

随便送一段波形进音乐厅,出来的波形通常面目全非;但如果送进去的是复指数 e2πifte^{2\pi i f t},出来的依然是同样频率的 e2πifte^{2\pi i f t},只是整体乘了一个复常数 H(f)H(f)(振幅缩放 ∣H(f)∣|H(f)| 倍,相位平移 arg⁡H(f)\arg H(f))。

复指数 e2πifte^{2\pi i f t} 是所有线性时不变系统的公共特征函数,H(f)H(f) 就是对应的特征值。 如果能把任意信号拆成单频复指数的叠加,卷积就会退化成按频率逐点相乘。

傅里叶变换#

怎么把一段混杂的信号 x(t)x(t) 拆成各个频率的分量?靠的还是正交抵消。

在区间 [0,T][0,T] 上,不同整数圈数的复指数 ek(t)=e2πikt/Te_k(t) = e^{2\pi i k t / T} 彼此正交:

1T∫0Tek(t)eℓ(t)‾ dt=1T∫0Te2πi(k−ℓ)t/T dt={1,k=ℓ,0,k≠ℓ.\frac{1}{T}\int_0^T e_k(t)\overline{e_\ell(t)}\,dt = \frac{1}{T}\int_0^T e^{2\pi i (k-\ell)t/T}\,dt = \begin{cases} 1, & k=\ell, \\ 0, & k\ne \ell. \end{cases}

想知道信号 x(t)x(t) 里含有多少频率 k/Tk/T 的成分,只需拿一根反向旋转的探针 e−2πikt/Te^{-2\pi i k t / T} 乘上去,再对一个周期求平均:

  • 信号里以 +k+k 圈旋转的成分,被探针的 −k-k 圈抵消了旋转,定格成常数,积分留住;
  • 其他频率 ℓ≠k\ell \ne k 的成分仍在绕原点旋转,转满整数圈后积分抵消为 00。
Winding a frequency-3 signal around the origin with mismatched and matched rotating probes. Winding a frequency-3 signal around the origin with mismatched and matched rotating probes.
把频率为 3 的信号绕在复平面原点上:当探针频率不匹配时(中),曲线围绕原点对称分布,质心归零;当探针频率与信号合拍时(右),波峰全部朝向同一侧,质心明显偏离原点。

这个地方 3b1b 形象展示傅里叶变换的视频 ↗ 讲的很好

当区间推向整条实数轴,离散频率变成连续频率 ff,就得到连续傅里叶变换与逆变换:

x^(f)=∫−∞∞x(t) e−2πift dt,x(t)=∫−∞∞x^(f) e2πift df.\widehat{x}(f) = \int_{-\infty}^{\infty} x(t)\,e^{-2\pi i f t}\,dt, \qquad x(t) = \int_{-\infty}^{\infty} \widehat{x}(f)\,e^{2\pi i f t}\,df.

对卷积 (x∗h)(t)(x*h)(t) 做变换,令 u=t−τu = t - \tau(t=u+τt = u + \tau),指数把位置相加拆成乘积,双重积分自然裂成两个独立积分之积(卷积定理):

x∗h^(f)=x^(f)⋅h^(f).\boxed{\widehat{x*h}(f) = \widehat{x}(f)\cdot \widehat{h}(f).}
直观例子:两个方波卷出三角形

取 [0,1][0,1] 上高度为 11 的矩形脉冲 p(t)p(t)。在时域里,(p∗p)(t)(p*p)(t) 是滑动区间 [t−1,t][t-1,t] 与 [0,1][0,1] 的重叠长度,是一条从 00 爬到 11 再降回 00 的三角形曲线。而在频域里,p^(f)=e−πifsin⁡(πf)πf\widehat{p}(f) = e^{-\pi i f}\frac{\sin(\pi f)}{\pi f},三角形脉冲的傅里叶变换无需再算积分,直接平方就是 p^(f)2\widehat{p}(f)^2。

(注:连续积分变换的严格存在性与反演条件通常在 L1(R)L^1(\mathbb R) 或 Schwartz 函数空间中讨论,可参阅华盛顿大学傅里叶讲义 ↗。)

DFT#

回到计算机里,我们手里只有长度为 NN 的有限序列 a0,a1,…,aN−1a_0, a_1, \ldots, a_{N-1}。

把连续积分换成有限求和,把探针换成 NN 次单位根 ωN=e−2πi/N\omega_N = e^{-2\pi i / N},就得到了离散傅里叶变换(DFT):

a^k=∑j=0N−1aj ωNjk,k=0,1,…,N−1.\widehat{a}_k = \sum_{j=0}^{N-1} a_j\,\omega_N^{jk}, \qquad k = 0, 1, \ldots, N-1.

对照前面写的多项式 A(x)=∑j=0N−1ajxjA(x) = \sum_{j=0}^{N-1} a_j x^j,就会看到:

a^k=A(ωNk).\boxed{\widehat{a}_k = A(\omega_N^k).}

信号处理里的离散傅里叶变换(DFT)就是把多项式 A(x)A(x) 代入全部 NN 个单位根 ωN0,ωN1,…,ωNN−1\omega_N^0, \omega_N^1, \ldots, \omega_N^{N-1} 算出的点值表示。

逆变换#

已知 NN 个单位根上的点值 a^0,…,a^N−1\widehat{a}_0, \ldots, \widehat{a}_{N-1},怎么把原来的系数 ara_r 捞回来?不必去解复杂方程组,直接用单位根正交求和——把每个 a^k\widehat{a}_k 乘上反向旋转的 ωN−kr\omega_N^{-kr} 加起来:

∑k=0N−1a^k ωN−kr=∑k=0N−1(∑j=0N−1ajωNjk)ωN−kr=∑j=0N−1aj(∑k=0N−1ωNk(j−r))⏟仅 j=r 时为 N,其余为 0=Nar.\sum_{k=0}^{N-1} \widehat{a}_k\,\omega_N^{-kr} = \sum_{k=0}^{N-1}\left(\sum_{j=0}^{N-1} a_j\omega_N^{jk}\right)\omega_N^{-kr} = \sum_{j=0}^{N-1} a_j \underbrace{\left(\sum_{k=0}^{N-1} \omega_N^{k(j-r)}\right)}_{\text{仅 }j=r\text{ 时为 }N\text{,其余为 }0} = N a_r.

两边除以 NN,逆变换直接出现:

ar=1N∑k=0N−1a^k ωN−kr.\boxed{a_r = \frac{1}{N}\sum_{k=0}^{N-1} \widehat{a}_k\,\omega_N^{-kr}.}

逆 DFT 和正 DFT 结构几乎完全对称,只是把 ωN\omega_N 换成共轭反方向 ωN−1\omega_N^{-1},最后除以 NN。所以写一个正变换加速(FFT),改个符号就能直接跑逆变换。

例子#

取 a=[1,2,0,0]a = [1, 2, 0, 0],对应 A(x)=1+2xA(x) = 1 + 2x。代入 4 次单位根 (1,−i,−1,i)(1, -i, -1, i):

a^0=A(1)=3,a^1=A(−i)=1−2i,a^2=A(−1)=−1,a^3=A(i)=1+2i.\widehat{a}_0 = A(1) = 3, \quad \widehat{a}_1 = A(-i) = 1-2i, \quad \widehat{a}_2 = A(-1) = -1, \quad \widehat{a}_3 = A(i) = 1+2i.

a^1=1−2i\widehat{a}_1 = 1-2i 和 a^3=1+2i\widehat{a}_3 = 1+2i 互为共轭。因为在整数采样点 jj 上,顺时针转 N−kN-k 格(ωN(N−k)j\omega_N^{(N-k)j})和逆时针转 kk 格(ωN−kj=ωNkj‾\omega_N^{-kj} = \overline{\omega_N^{kj}})重合。对任何实数序列都有 a^N−k=a^k‾\widehat{a}_{N-k} = \overline{\widehat{a}_k},后半段编号 k>N/2k > N/2 的频点其实就是负频率 k−Nk-N。

交互实验 · 频率探针 在实验室中打开 →

用反向旋转去“抵消”信号中的某个频率

频率探针参数
X2=∑j=015xj ω162j=0X_{2}=\sum_{j=0}^{15}x_j\,\omega_{16}^{2j}=0
信号 x_j
0123456789101112131415频谱 |X_k|(点击选 k)橙色:镜像 X₁₄
把每项转 jk 格后首尾相接

箭头首尾相接围成闭合多边形,总和回到原点:这个频率转完整数圈,方向彼此抵消,信号里没有它。

循环卷积#

如果拿两个长度为 NN 的序列 a,ba, b,各自做 DFT 得到 a^k,b^k\widehat{a}_k, \widehat{b}_k,逐点相乘 c^k=a^kb^k\widehat{c}_k = \widehat{a}_k \widehat{b}_k,再做逆 DFT 回来,得到的是普通卷积吗?

未必。展开 C(x)=A(x)B(x)C(x) = A(x)B(x),最高次数可达 2N−22N-2。但在 NN 次单位根上,(ωNk)N=1(\omega_N^k)^N = 1,所有次数达到或超过 NN 的项都会折返:

(ωNk)N+r=(ωNk)N⋅(ωNk)r=(ωNk)r.(\omega_N^k)^{N+r} = (\omega_N^k)^N \cdot (\omega_N^k)^r = (\omega_N^k)^r.

在 NN 次单位根眼里,xN+rx^{N+r} 和 xrx^r 无法区分。原本属于第 N+rN+r 号位置的系数 cN+rc_{N+r} 会绕回来,叠加到第 rr 号位置上:

ckcyc=∑j=0N−1aj b(k−j) mod N=ck+ck+N+ck+2N+⋯c_k^{\mathrm{cyc}} = \sum_{j=0}^{N-1} a_j\, b_{(k-j)\bmod N} = c_k + c_{k+N} + c_{k+2N} + \cdots

这就是循环卷积。以 a=[1,2,3],b=[4,5,6]a=[1,2,3], b=[4,5,6] 为例,普通卷积有 5 项:[4,13,28,27,18][4, 13, 28, 27, 18]。若只用长度 N=4N=4 的 DFT 去算,18x418x^4 会按 x4=1x^4=1 折回常数项,算出 [4+18,13,28,27]=[22,13,28,27][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−1n+m-1 项,篮子只有 N<n+m−1N < n+m-1 个,溢出了。

只要事先选变换长度 N≥n+m−1N \ge n+m-1,把两个输入序列末尾都补上 00 扩充到长度 NN,乘积中就不会出现次数 ≥N\ge N 的非零项,自然没有任何项会绕回来。

两个长度为 3 的序列相乘,结果有 5 项;配合基 2 FFT 选最小的 2 的幂 N=8N=8 补零,循环卷积算出的前 5 项就和普通卷积完全一致。

代数视角:多项式环上的中国剩余定理

在单位根上求值,等价于把多项式对 xN−1=∏k=0N−1(x−ωNk)x^N - 1 = \prod_{k=0}^{N-1}(x - \omega_N^k) 取模。由中国剩余定理,商环分解为 NN 个独立复数域的直积:

C[x]/(xN−1)  ≅  ∏k=0N−1C[x]/(x−ωNk)  ≅  CN,[A(x)]⟼(A(1),A(ωN),…,A(ωNN−1)).\mathbb C[x]/(x^N - 1) \;\cong\; \prod_{k=0}^{N-1} \mathbb C[x]/(x - \omega_N^k) \;\cong\; \mathbb C^N, \qquad [A(x)] \longmapsto \bigl(A(1), A(\omega_N), \ldots, A(\omega_N^{N-1})\bigr).

左边的乘法是模 xN=1x^N=1 的循环卷积,右边是逐坐标相乘,而连接两边的同构映射正是 DFT。

FFT#

现在可以把前面为单位根埋下的伏笔全部兑现了。快速计算 DFT 的算法叫快速傅里叶变换(FFT)(Cooley 与 Tukey 于 1965 年发表,高斯早在 1805 年手稿中便已使用)。这里以最经典的基 2 版本(N=2sN = 2^s)为例。

奇偶拆分#

把 A(x)=a0+a1x+⋯+aN−1xN−1A(x) = a_0 + a_1 x + \cdots + a_{N-1} x^{N-1} 的偶数下标项和奇数下标项分成两半:

A(x)=(a0+a2x2+a4x4+⋯ )+x(a1+a3x2+a5x4+⋯ )=E(x2)+x O(x2),\begin{aligned} A(x) &= (a_0 + a_2 x^2 + a_4 x^4 + \cdots) + x(a_1 + a_3 x^2 + a_5 x^4 + \cdots) \\ &= E(x^2) + x\,O(x^2), \end{aligned}

其中 E(z)=∑j=0N/2−1a2jzjE(z) = \sum_{j=0}^{N/2-1} a_{2j} z^j 和 O(z)=∑j=0N/2−1a2j+1zjO(z) = \sum_{j=0}^{N/2-1} a_{2j+1} z^j 是两个长度只有 N/2N/2 的多项式。

蝶形运算#

对前半圈 0≤k<N/20 \le k < N/2,把 x=ωNkx = \omega_N^k 和它对面的 x=ωNk+N/2x = \omega_N^{k+N/2} 同时代入。利用单位根的折半性((ωNk)2=(ωNk+N/2)2=ωN/2k(\omega_N^k)^2 = (\omega_N^{k+N/2})^2 = \omega_{N/2}^k)和对称性(ωNk+N/2=−ωNk\omega_N^{k+N/2} = -\omega_N^k),得到:

a^k=E(ωN/2k)+ωNk O(ωN/2k),a^k+N/2=E(ωN/2k)−ωNk O(ωN/2k).\begin{aligned} \widehat{a}_k &= E(\omega_{N/2}^k) + \omega_N^k\, O(\omega_{N/2}^k), \\ \widehat{a}_{k+N/2} &= E(\omega_{N/2}^k) - \omega_N^k\, O(\omega_{N/2}^k). \end{aligned}

记 u=E(ωN/2k)u = E(\omega_{N/2}^k)、v=ωNkO(ωN/2k)v = \omega_N^k O(\omega_{N/2}^k),前后半圈的一对输出直接共享同一次计算:

(a^k, a^k+N/2)=(u+v, u−v).\boxed{(\widehat{a}_k,\ \widehat{a}_{k+N/2}) = (u + v,\ u - v).}

这就是蝶形运算。一次长度为 NN 的 DFT 拆成两次长度为 N/2N/2 的子 DFT,再加上 N/2N/2 次蝶形合并:

T(N)=2T(N/2)+O(N)  ⟹  T(N)=O(Nlog⁡N).T(N) = 2T(N/2) + O(N) \implies \boxed{T(N) = O(N\log N).}

当 N=220≈106N = 2^{20} \approx 10^6 时,N2≈1012N^2 \approx 10^{12},而 N2log⁡2N≈107\frac{N}{2}\log_2 N \approx 10^7,运算量缩小了五个数量级。以 a=[1,2,0,0]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

交互实验 · FFT 蝶形 在实验室中打开 →

一对求值点共享一次计算

FFT 蝶形参数
输入按下标的 3 位二进制反转排列:0,4,2,6,1,5,3,70,4,2,6,1,5,3,7
10302040输入(位反转序)········长度 2 的 DFT········长度 4 的 DFT········长度 8 的 DFTa₀a₄a₂a₆a₁a₅a₃a₇X₀X₁X₂X₃X₄X₅X₆X₇

点“下一层”开始合并。每一层都可以点击右侧一列的某个节点,查看算出它的那次蝶形。

2 个根,平方后剩 1 个
直接按定义
64 次复数乘法
FFT 已用
0 / 12 次蝶形

迭代实现中的位反转#

递归写法很直观,但迭代版 FFT 开头总要做一次“二进制位反转(Bit-Reversal)”重排。以 N=8N=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=8N=8 的三层蝶形完整计算表

取 a=[1,2,3,4,0,0,0,0]a=[1,2,3,4,0,0,0,0](即 A(x)=1+2x+3x2+4x3A(x)=1+2x+3x^2+4x^3)。按位反转序 [0,4,2,6,1,5,3,7] 重排后,输入变为 [1, 0, 3, 0, 2, 0, 4, 0]:

层旋转因子当前各块结果
位反转输入—1, 0, 3, 0, 2, 0, 4, 01,\ 0,\ 3,\ 0,\ 2,\ 0,\ 4,\ 0
第 1 层(块长 2)ω20=1\omega_2^0=11,1 ∣ 3,3 ∣ 2,2 ∣ 4,41,1\ \mid\ 3,3\ \mid\ 2,2\ \mid\ 4,4
第 2 层(块长 4)ω40=1, ω41=−i\omega_4^0=1,\ \omega_4^1=-i4, 1−3i, −2, 1+3i ∣ 6, 2−4i, −2, 2+4i4,\ 1-3i,\ -2,\ 1+3i\ \mid\ 6,\ 2-4i,\ -2,\ 2+4i
第 3 层(块长 8)ω8k=(1−i)k/2k\omega_8^k=(1-i)^k/\sqrt{2}^k见下表

第 3 层以左半第 kk 项作 uu、右半第 kk 项乘 ω8k\omega_8^k 作 vv:

kkuuvva^k=u+v\widehat a_k=u+va^k+4=u−v\widehat a_{k+4}=u-v
0044661010−2-2
111−3i1-3i−2−32 i-\sqrt2-3\sqrt2\,i(1−2)−(3+32)i(1-\sqrt2)-(3+3\sqrt2)i(1+2)+(32−3)i(1+\sqrt2)+(3\sqrt2-3)i
22−2-22i2i−2+2i-2+2i−2−2i-2-2i
331+3i1+3i2−32 i\sqrt2-3\sqrt2\,i(1+2)+(3−32)i(1+\sqrt2)+(3-3\sqrt2)i(1−2)+(3+32)i(1-\sqrt2)+(3+3\sqrt2)i

三层总共做了 3×4=123\times 4 = 12 次蝶形,而按 DFT 定义直接算需要 82=648^2 = 64 次复数乘法。

用 FFT 计算多项式乘法#

算一次 (1+2x)(3+4x)(1+2x)(3+4x):

  1. 补零:结果最多有 2+2−1=32+2-1=3 项,取 N=4N=4,补成 a=[1,2,0,0]a=[1,2,0,0],b=[3,4,0,0]b=[3,4,0,0]。
  2. 正变换:代入 ω4=−i\omega_4 = -i 的幂 (1,−i,−1,i)(1, -i, -1, i): a^=[3, 1−2i, −1, 1+2i],b^=[7, 3−4i, −1, 3+4i].\widehat{a} = [3,\ 1-2i,\ -1,\ 1+2i], \qquad \widehat{b} = [7,\ 3-4i,\ -1,\ 3+4i].
  3. 逐点相乘: c^=[21, −5−10i, 1, −5+10i].\widehat{c} = [21,\ -5-10i,\ 1,\ -5+10i].
  4. 逆变换:用 ω4−1=+i\omega_4^{-1} = +i 求平均:
    • c0=14[21+(−5−10i)+1+(−5+10i)]=3c_0 = \frac{1}{4}[21 + (-5-10i) + 1 + (-5+10i)] = 3;
    • c1=14[21+(−5−10i)i−1+(−5+10i)(−i)]=10c_1 = \frac{1}{4}[21 + (-5-10i)i - 1 + (-5+10i)(-i)] = 10;
    • 同理 c2=8, c3=0c_2 = 8,\ c_3 = 0。

得到 C(x)=3+10x+8x2C(x) = 3 + 10x + 8x^2,与直接展开完全一致。

NTT#

复数 FFT 的精度边界#

公式里的 cos⁡(2π/N)\cos(2\pi/N) 和 sin⁡(2π/N)\sin(2\pi/N) 是精确的,但放进 64 位双精度浮点数(double)后,无理数在第一步就会被截断。经过 log⁡2N\log_2 N 层蝶形运算的舍入累积,原本是整数 33 的系数算出来往往像这样:

2.9999999999997+0.0000000000001i.2.9999999999997 + 0.0000000000001i.

只要实部的绝对误差严格小于 0.50.5,四舍五入就能无损恢复。但随着系数变大、序列变长,误差会迅速逼近这条红线。下面是一组实测(两个长度 10241024、非负整数系数在 [0,B)[0, B) 内的多项式,用标准双精度基 2 FFT 算长度 N=2048N=2048 卷积,对照 BigInt 真值):

系数上界 BB乘积最大真实系数实部最大绝对误差四舍五入错误的系数个数
10310^32.69×1082.69\times 10^87.45×10−87.45\times 10^{-8}00
10510^52.70×10122.70\times 10^{12}0.000730.0007300
10610^62.70×10142.70\times 10^{14}0.093750.0937500
5×1065\times 10^66.74×10156.74\times 10^{15}2.52.512061206(共 2047 项)

double 能精确表示的最大连续整数是 253≈9.007×10152^{53} \approx 9.007\times 10^{15},最后一行的真实乘积最大才 6.74×10156.74\times 10^{15},装得进 double但十层蝶形算完后实部误差已经达到 2.52.5,超过一半的系数取整出错。

有限域里的单位根#

既然误差来自复数单位根里的无理数,不妨回头检查一下:推导 DFT 和基 2 FFT 时,我们到底用到了复数的什么性质?

其实只用了三条纯代数性质:

  1. 存在一个元素 ω\omega,其 NN 次幂为 11,且前 NN 次幂互不相同(保证正交求和为 00);
  2. 支持加、减、乘,且 NN 有乘法逆元(保证逆变换能除以 NN);
  3. 当 NN 为偶数时,ωN/2=−1\omega^{N/2} = -1 且 ωN2=ωN/2\omega_N^2 = \omega_{N/2}(保证奇偶拆分和蝶形合并)。

只要在一个纯整数的代数世界里找到满足这三条的元素,就能把整套 FFT 代码原样搬过去,全程整数运算、零舍入误差。这个世界就是模素数 pp 的有限域 Fp\mathbb F_p,搬过去后的算法叫数论变换(NTT)。

对任何素数 pp,Fp\mathbb F_p 中非零元素在模 pp 乘法下构成阶为 p−1p-1 的循环群,其生成元叫原根 gg(g1,…,gp−1 mod pg^1, \ldots, g^{p-1} \bmod p 跑遍所有非零余数)。只要 N∣(p−1)N \mid (p-1),令:

w=g(p−1)/N(modp),w = g^{(p-1)/N} \pmod p,

ww 就满足 wN≡1(modp)w^N \equiv 1 \pmod p、wN/2≡−1(modp)w^{N/2} \equiv -1 \pmod p,并且平方后阶恰好减半,具备单位根的全部代数脾气。

这也是算法竞赛里 998244353998244353 如此常见的原因:

998244353−1=119×223.998244353 - 1 = 119 \times 2^{23}.

它包含足足 2323 个因子 22(且原根是 g=3g=3),支持长度最高达 2232^{23} 的基 2 NTT。相比之下,常用的 109+710^9+7 减 11 后只含一个因子 22,连长度 44 的基 2 NTT 都无法运行。

示例#

拿 [1,2,3]∗[4,5,6]=[4,13,28,27,18][1,2,3]*[4,5,6] = [4,13,28,27,18] 做一次长度 N=8N=8 的 NTT。 取 p=17p=17(8∣168 \mid 16,原根 g=3g=3,w=316/8=9(mod17)w = 3^{16/8} = 9 \pmod{17},8−1≡15(mod17)8^{-1} \equiv 15 \pmod{17}),算完得到:

[4, 13, 11, 10, 1, 0, 0, 0](mod17).[4,\ 13,\ 11,\ 10,\ 1,\ 0,\ 0,\ 0] \pmod{17}.

NTT 没有误差,但它只记录模 1717 的余数。要让余数直接等于真实非负整数系数,模数 pp 必须大于最大真实系数 2828 且满足 8∣(p−1)8 \mid (p-1)。顺着往后找,第一个满足条件的素数是 p=41p=41(41−1=40=8×541-1=40=8\times 5,原根 g=6g=6,w=65≡27(mod41)w=6^5 \equiv 27 \pmod{41}),换用模 41 算出的就是精确的 [4,13,28,27,18,0,0,0][4, 13, 28, 27, 18, 0, 0, 0]。

若真实系数超过单个 NTT 素数,可以选两三个互素的 NTT 素数分别计算,再用中国剩余定理(CRT) 拼回大整数(参考 AtCoder Library 的 convolution 说明 ↗)

大致对应关系:

概念复数域 FFT有限域 NTT
空间C\mathbb{C}(复数)Fp\mathbb{F}_p(模素数 pp 的整数)
单位根ω=e2πi/N\omega = e^{2\pi i / N}w=g(p−1)/N mod pw = g^{(p-1)/N} \bmod p
逆变换除以 NN乘以 1/N1/N乘以 N−1(modp)N^{-1} \pmod p
ωN/2\omega^{N/2}−1-1 (复数)p−1p-1 (整数)
误差有浮点舍入误差无误差

交互实验 · 完整算例 在实验室中打开 →

补零、变换、相乘、逆变换,一步一步算完

完整算例参数
a=1+2x, b=3+4xa=1+2x,\ b=3+4x,乘积次数为 2,需要 3 个系数,取 N=4N=4 并补零
  1. 补零
  2. 变换 a
  3. 变换 b
  4. 逐点相乘
  5. 逆变换
  6. 读出结果
kkaka_kbkb_ka^k\hat a_kb^k\hat b_kc^k=a^kb^k\hat c_k=\hat a_k\hat b_k逆变换的实部\text{逆变换的实部}取整\text{取整}
013·····
124·····
200·····
300·····

每一步都在表里新增一列。灰色的列还没有算到。

本面板实际调用与蝶形实验相同的基 2 FFT;逆变换使用共轭、正变换和除以 N。它展示的是这组输入的计算结果,不能作为所有 FFT 实现的误差界。

延伸阅读#

2026 年 10 月 6 日,OpenAI 发布了一大坨数学成果,不乏各种领域的硕大果实,其中在计算机科学领域,矩阵乘法复杂度上界降至 ω(C)≤2.25\omega(\mathbb{C}) \le 2.25 的突破 大概最为亮眼,在这里边就有涉及到了 FFT 相关内容。

本来这个文章是为了讲矩阵乘法的突破的,不过奈何感觉很难以科普的口吻讲出来,所以做了巨量删减。由于要处理事情还蛮多的,对于这个部分的内容就先暂缓吧。 对于矩阵复杂度突破历史推荐看矩阵乘法的复杂度能达到多低? ↗

FFT
https://fxj.wiki/blog/convolution-to-fft
Author 玛卡巴卡
Published at 2026年10月20日
Comment seems to stuck. Try to refresh?✨