跳到主要内容

从卷积到 FFT

十二个可以拖动的实验:卷积的乘积表、点值与单位根、复数旋转、欧拉级数、频率探针、FFT 蝶形与完整算例、NTT、循环矩阵的对角化、Karatsuba、Strassen 和矩阵编码。

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

用“演奏家、音乐厅、听众”三个角色看卷积:演奏家视角里,每一拍输入 aia_i 在 t=it=i 响起后向右拖出按 bb 衰减的余音,此刻听到的总声 ckc_k 就是所有未散尽余音的垂直叠加;听众视角里,固定此刻 kk 往过去回看,时间差 k−τk-\tau 让响应 bb 翻转并平移,重叠处相乘再相加(即乘积表的斜线 i+j=ki+j=k)。切换到连续小提琴,可以看到连续信号 x(τ)x(\tau) 切成薄片 x(τj)Δτx(\tau_j)\Delta\tau 后如何收敛到卷积积分 ∫0tx(τ)h(t−τ) dτ\int_0^t x(\tau)h(t-\tau)\,d\tau。

卷积参数
离散预设
a 的长度 b 的长度
c2=∑i+j=2aibj=a0b2+a1b1+a2b0=2⋅0.3+3⋅0.6+1.5⋅1=3.71c_{2}=\sum_{i+j=2}a_ib_j=a_{0}b_{2}+a_{1}b_{1}+a_{2}b_{0}=2\cdot0.3+3\cdot0.6+1.5\cdot1=3.71
第 0 拍 (a₀=2)余音衰减 →0.56第 1 拍 (a₁=3)余音衰减 →1.65第 2 拍 (a₂=1.5)余音衰减 →1.5听众听到的总声各拍余音叠加2t=04.1t=13.71t=21.91t=30.78t=40.18t=5听众此刻 t=2:总音量 3.71
2a03a11.5a2输入 a:每一下的强度
1b00.6b10.3b20.1b3响应 b:一下之后每格的余音
列 j:余音 b10.60.30.1221.10.60.2331.70.80.41.51.50.80.40.2行 i
2c04.1c13.7c21.9c30.8c40.2c5

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

A(x)B(x)=(2+3x+1.5x2)(1+0.55x+0.28x2+0.12x3)=2+4.1x+3.71x2+1.91x3+0.78x4+0.18x5A(x)B(x)=(2+3x+1.5x^{2})(1+0.55x+0.28x^{2}+0.12x^{3})=2+4.1x+3.71x^{2}+1.91x^{3}+0.78x^{4}+0.18x^{5}

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

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

次数小于 nn 的多项式由 nn 个互不相同点上的值唯一确定。在点值表示下,乘法只是把同一点上的两个值相乘。(1+2x)(3+4x)(1+2x)(3+4x) 的次数是 2,需要 3 个点才能插值回来。把求值点换成单位根,求值就是 DFT,插值就是逆 DFT。下方的条件数表说明单位根还有一个好处:固定矩阵时,2 范数相对误差的条件数为 1;实际计算仍会舍入。

点值表示参数
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。

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

z=reiθz=re^{i\theta} 乘上 w=seiϕw=se^{i\phi},长度相乘、角度相加:zw=rs ei(θ+ϕ)zw=rs\,e^{i(\theta+\phi)}。拖动 zz 和 ww,看单位方格怎样被整体旋转和缩放。连按“z ← zw”,点就在一圈圈地转:复数把“旋转”变成了乘法,后面的单位根和傅里叶都靠这一点。

复数乘法参数
把 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 之后的样子。整个平面被同一个复数旋转并缩放,方格依旧是方格:乘法不会把平面拉歪。

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

eiθ=∑(iθ)n/n!e^{i\theta}=\sum (i\theta)^n/n!。每一项是上一项乘 iθ/(n+1)i\theta/(n+1):乘 ii 转 90°,乘 θ/(n+1)\theta/(n+1) 改变长度。前几项可能越来越长,但阶乘最终压过 θn\theta^n,折线一边左转一边收缩,停在单位圆上角度为 θ\theta 的点。下方的对数柱图显示各项长度在 n≈θn\approx\theta 处最大,较大的项相消会增加舍入风险,有限项截断则是另一种误差。

欧拉公式参数
θ=π,∑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 项,θ 较大时截断误差仍可能很大;继续增加项数与控制浮点误差是两个问题。

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

ωr\omega^r 每次转 r/Nr/N 圈。把 1,ωr,ω2r,…1,\omega^r,\omega^{2r},\ldots 首尾相接:只要 N∤rN\nmid r,折线就会闭合,和为 0;N∣rN\mid r 时每一项都是 1,和为 NN。逆 DFT 和卷积定理的证明都只用到这一个恒等式。把所有 rr 的和排成矩阵,就是 FF∗=NIFF^*=NI。

单位根参数
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,不需要另解方程。

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

Xk=∑jxj ωjkX_k=\sum_j x_j\,\omega^{jk}:把第 jj 个采样乘以 ωjk\omega^{jk},也就是转 jk/16jk/16 圈,再首尾相接。对于单个整数频率的复指数,匹配的探针让它停止旋转,其余探针累加为 0。本实验使用实余弦,包含正、负两个方向的分量,需要分别考虑。实信号的频率 kk 同时出现在镜像位置 16−k16-k。信号频率超过 8 时,16 个采样已经分不清它和更低的频率;“频率再加半圈”让信号落在两个探针之间,通常会在多个频点出现泄漏分量。

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

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

一对求值点共享一次计算

A(x)=E(x2)+x O(x2)A(x)=E(x^2)+x\,O(x^2)。ωk\omega^k 和 ωk+N/2=−ωk\omega^{k+N/2}=-\omega^k 互为相反数,平方相同,所以两处的 E,OE,O 是同一个值,只差 xx 前面的符号:(u+v,  u−v)(u+v,\;u-v)。右边的圆显示这一点:NN 个单位根平方后两两重合,问题规模减半,一共 log⁡2N\log_2N 层。可以改 NN、自己输入序列,点任意一个蝶形看它的两个输入和两个输出。

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 乘多项式分六步:补零到足够长,分别变换两个系数序列,逐点相乘,逆变换,最后读出整数。复数版本有浮点误差,只有实部误差小于 1/2 时,取整才保证恢复整数;NTT 在模 pp 的整数里做同样的事,没有误差,但只能得到余数。换成“大系数”可以看到:结果超过 pp 时需要更大的素数,或用几个素数的余数经中国剩余定理拼回来。

完整算例参数
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 实现的误差界。

傅里叶变换对角化了什么

循环卷积写成矩阵 CbC_b,每一列是上一列循环下移一格,即 Cb=∑rbrPrC_b=\sum_r b_rP^r,其中 PP 是循环移位。傅里叶向量是 PP 的特征向量(移一格只乘一个单位根),所以也是任何 PP 的多项式的特征向量。换到这组基下,卷积变成了逐点乘法。去掉绕回项得到普通卷积的 Toeplitz 矩阵,它不再是对角的,要先补零嵌进更大的循环矩阵。

循环矩阵参数
FCbF−1=diag⁡(b^)=diag⁡(15, −2−5i, 5, −2+5i)FC_bF^{-1}=\operatorname{diag}(\hat b)=\operatorname{diag}(15,\,-2-5i,\,5,\,-2+5i)
循环矩阵 C_b4065540665400654
换到傅里叶坐标150000−2−5i000050000−2+5i

每一列都是上一列向下循环挪一格,所以 C_b = b₀I + b₁P + b₂P² + b₃P³。傅里叶向量是 P 的特征向量,于是也是 C_b 的特征向量:对角线上依次是 b 的 DFT,对角线外全是 0。

三次乘法换掉四次,交叉项从和里减出来

(a0+a1x)(b0+b1x)(a_0+a_1x)(b_0+b_1x) 的中间项只需要 a0b1+a1b0a_0b_1+a_1b_0 这个和。一次 (a0+a1)(b0+b1)(a_0+a_1)(b_0+b_1) 同时算出四个格子,减去两个对角格就得到它。系数可以换成半长的多项式,于是 T(n)=3T(n/2)+O(n)T(n)=3T(n/2)+O(n),T(n)=O(nlog⁡23)T(n)=O(n^{\log_23})。

Karatsuba参数
a=a=
b=b=
3 次乘法:8+10x+3x2;代入 x=10:12×34=408\text{3 次乘法:}8+10x+3x^{2}\text{;代入 }x=10\text{:}12\times34=408

直接展开:四个格子,四次乘法

b0=4b_0=4
b1=3b_1=3
a0=2a_0=2
a₀b₀ = p₀8
a₀b₁6
a1=1a_1=1
a₁b₀4
a₁b₁ = p₁3

两个对角格是 p0p_0 和 p1p_1。另外两个格子只需要它们的和,p2p_2 把四个格子一起算出来,减去两个对角格就得到。

Karatsuba:三次乘法

  1. p0=a0b0=8p_0=a_0b_0=8
  2. p1=a1b1=3p_1=a_1b_1=3
  3. p2=(a0+a1)(b0+b1)=3⋅7=21p_2=(a_0+a_1)(b_0+b_1)=3\cdot7=21

a0b1+a1b0=p2−p0−p1=10a_0b_1+a_1b_0=p_2-p_0-p_1=10

(a0+a1x)(b0+b1x)=8+10x+3x2(a_0+a_1x)(b_0+b_1x)=8+10x+3x^{2}

同一件事:在 0、1、∞ 三个点求值再插值

C(0)=a0b0=p0,C(1)=(a0+a1)(b0+b1)=p2,C(∞)=a1b1=p1C(0)=a_0b_0=p_0,\quad C(1)=(a_0+a_1)(b_0+b_1)=p_2,\quad C(\infty)=a_1b_1=p_1

c1=C(1)−C(0)−C(∞)=21−8−3=10c_1=C(1)-C(0)-C(\infty)=21-8-3=10

C(∞)C(\infty) 指最高次系数。次数为 2 的乘积由 3 个点值确定,每个点值各要一次乘法,所以是 3 次。这正是“点值表示”实验的思路,只是点选得特别便宜。

把每个系数换成半长的多项式,递归 4 层(n = 16)

只数乘法:44=2564^{4}=256 对 34=813^{4}=81,剩 31.6%,指数从 2 降到 log⁡23≈1.585\log_2 3\approx 1.585。每层还要做 4n−44n-4 次加减(两次求和、两次相减、拼接时的重叠相加)。下表把乘法和加法都算上(直接算法 n2+(n−1)2n^2+(n-1)^2 次):

n直接算法递归到底比值最佳切换块比值
255771.40不递归1.00
4252533331.32不递归1.00
81131131271271.1240.91
164814814414410.9240.77
321,9851{,}9851,4471{,}4470.7340.62
648,0658{,}0654,5934{,}5930.5740.49
12832,51332{,}51314,28714{,}2870.4440.38
256130,561130{,}56143,88143{,}8810.3440.29
512523,265523{,}265133,687133{,}6870.2640.22
10242.10×1062.10\times10^{6}405,153405{,}1530.1940.17

比值小于 1 才说明更省。“最佳切换块”指递归到这个大小就改用直接算法,取总次数最少的那个。递归到底在 n=16 才开始省;在长度 4 处切换,n=8 就能省约 9%,n=64 能省一半。

七次乘法换掉八次,递归之后指数下降

普通 2×22\times2 矩阵乘法要 8 个乘积。Strassen 先做加减,造出 7 个乘积,再只靠加减拼回结果;多出来的项在拼接时互相抵消。因为整个过程没有用到乘法交换律,数字可以换成矩阵块,于是 T(n)=7T(n/2)+O(n2)T(n)=7T(n/2)+O(n^2),T(n)=O(nlog⁡27)T(n)=O(n^{\log_27})。

Strassen参数
A=A=
B=B=
7 次乘法得到 AB=(19224350),与直接计算一致\text{7 次乘法得到 }AB=\begin{pmatrix}19&22\\43&50\end{pmatrix}\text{,与直接计算一致}

M₁ 展开后落在哪些格子

C₁₁
A 的元素efgh
a+1+1
b
c
d+1+1
C₁₂
A 的元素efgh
a
b
c
d
C₂₁
A 的元素efgh
a
b
c
d
C₂₂
A 的元素efgh
a+1+1
b
c
d+1+1

每张表的第 ii 行第 jj 列是单项 xiyjx_iy_j(如 aeae)在该输出里的系数,框出的是这个输出真正需要的两项。+1 和 −1 是这个乘积带进来的项,框外的必须由别的乘积抵消。

点开一个乘积

  • C₁₁(系数 +1):提供 ae;+ah 被 −M₅ 抵消;+de 被 −M₄ 抵消;+dh 被 −M₇ 抵消
  • C₂₂(系数 +1):提供 dh;+ae 被 −M₆ 抵消;+ah 被 −M₃ 抵消;+de 被 −M₂ 抵消

把数字换成矩阵块,递归 4 层(n = 16)

只数乘法:84=4,0968^{4}=4{,}096 对 74=2,4017^{4}=2{,}401,剩 58.6%,指数从 3 降到 log⁡27≈2.807\log_2 7\approx 2.807。但每层还要做 18 次块加减。下表把乘法和加法都算上(直接算法 2n3−n22n^3-n^2 次):

n直接算法递归到底比值最佳切换块比值
2121225252.08不递归1.00
41121122472472.21不递归1.00
89609602,0172{,}0172.10不递归1.00
167,9367{,}93615,27115{,}2711.9280.99
3264,51264{,}512111,505111{,}5051.7380.93
64520,192520{,}192798,967798{,}9671.5480.84
1284.18×1064.18\times10^{6}5.67×1065.67\times10^{6}1.3680.75
2563.35×1073.35\times10^{7}4.00×1074.00\times10^{7}1.1980.66
5122.68×1082.68\times10^{8}2.81×1082.81\times10^{8}1.0580.58
10242.15×1092.15\times10^{9}1.97×1091.97\times10^{9}0.9280.51

比值小于 1 才说明更省。“最佳切换块”指递归到这个大小就改用直接算法,取总次数最少的那个。递归到底要到 n=1024 才比直接算法少;在 8×8 处切换,n=64 就能省 16%。

把矩阵乘法塞进一次多项式乘法

把 AA、BB 的元素放到精心挑选的次数上,让 CijC_{ij} 需要的两项恰好落在同一个次数,其他乘积落在别处。这样一次多项式乘法就算出了 ABAB;代价是多项式长度涨到 Θ(n3)\Theta(n^3),大部分系数都是用不上的交叉项。切换 QQ 的次数安排,可以看到间隔太小时各个 CijC_{ij} 怎样撞在一起。

矩阵编码参数
A=A=
B=B=
[x1] PQ=a11b11+a12b21=1⋅5+2⋅7=19=C11[x^{1}]\,PQ=a_{11}b_{11}+a_{12}b_{21}=1\cdot5+2\cdot7=19=C_{11}

P(x) Q(x)P(x)\,Q(x) 的 16 个乘积,标出各自的次数

Q(x)=b21+b11x1+b22x4+b12x5Q(x)=b_{21}+b_{11}x^{1}+b_{22}x^{4}+b_{12}x^{5}

b₂₁·x⁰b₁₁·x¹b₂₂·x⁴b₁₂·x⁵
a₁₁·x⁰x⁰7x¹5x⁴8x⁵6
a₁₂·x¹x¹14x²10x⁵16x⁶12
a₂₁·x²x²21x³15x⁶24x⁷18
a₂₂·x³x³28x⁴20x⁷32x⁸24

按次数合并,读出四个位置

AB=(19224350)AB=\begin{pmatrix}19&22\\43&50\end{pmatrix},与直接计算一致。

每个 CijC_{ij} 的两项落在同一个次数上,而且那一格没有别的乘积。间隔再小一点,就会有项撞到一起,可以切换试试。点击某一次的系数,左表中落到这一格的乘积会被标出;红框是 AB 需要、却没有单独落在一格里的乘积。

有用的系数只占一小部分

一般的编码需要 n3+n−1n^3+n-1 个系数位置,其中只有 n2n^2 个是 ABAB 的元素。即使多项式乘法只需 O(Nlog⁡N)O(N\log N),这里的 NN 也已经是 Θ(n3)\Theta(n^3),并不比直接计算更快。

阅读说明与延伸问题

这条线怎样连起来#

十二个实验按文章的顺序走完一条线:

  1. 卷积:输出的第 kk 项收集所有 i+j=ki+j=k 的乘积 aibja_ib_j。多项式乘法也是这样收集系数。拖动“循环长度”可以把下标改成按 NN 取余,看补零和绕回的区别。打开“频域”,可以看到同一个结果在 DFT 之后变成逐点相乘。
  2. 点值表示:在 nn 个点上求值,多项式乘法就变成逐点相乘。点数少于乘积的系数个数时,插值会得到另一个多项式。条件数表比较了实数点和单位根插值的数值稳定性。
  3. 复数乘法:长度相乘,角度相加,旋转因此可以写成乘法。
  4. 欧拉公式:eiθe^{i\theta} 的级数每一项都比上一项多转 90°,部分和绕成螺旋,最后落在单位圆上。对数柱图标出最长的一项,帮助观察相消与舍入风险;有限项截断误差另外存在,不能由最长项直接推算。
  5. 单位根:ωrj\omega^{rj} 沿圆周跳动。只要 rr 不是 NN 的倍数,这些箭头首尾相接后回到原点,和为零。把这些和排成矩阵就是 FF∗=NIFF^*=NI。
  6. 频率探针:DFT 用反向旋转去比较信号。对单个整数频率的复指数,匹配频率时旋转被抵消,其余频点累加为零。本实验用实余弦,正负频率会形成一对共轭分量。余弦频率不是整数时,通常会出现多个频点的泄漏分量;还要考虑正负频率、相位和共轭对称。
  7. FFT:ωk\omega^k 与 −ωk-\omega^k 的平方相同,一对输出共享一次计算,每一层把问题规模减半。
  8. 完整算例:补零、两次变换、逐点相乘、逆变换,一步一步算出 (1+2x)(3+4x)(1+2x)(3+4x)。切到 NTT,在模 pp 的整数里重做一遍:模 17 时超过模数的系数会被折回,换更大的素数,或打开“大系数”用两个素数的余数经中国剩余定理拼回结果。
  9. 循环矩阵:循环卷积是移位算子 PP 的多项式。傅里叶向量是 PP 的特征向量,所以傅里叶变换把卷积矩阵变成对角矩阵。去掉绕回得到的 Toeplitz 矩阵不再能对角化,要先补零嵌进更大的循环矩阵。
  10. Karatsuba:两个一次多项式相乘本来要 4 次乘法,用 (a0+a1)(b0+b1)(a_0+a_1)(b_0+b_1) 一次得到两个交叉项之和,只需 3 次。
  11. Strassen:一般矩阵没有循环结构,但可以先做加减,再用 7 个乘积代替 8 个,递归下去指数就降到 log⁡27\log_2 7。
  12. 矩阵编码:把 2×22\times2 矩阵的元素放到不同次数上,多项式乘积的四个系数恰好是 ABAB 的四个元素。其余系数都是用不上的交叉项,这也是这种编码无法直接加速的原因。把 QQ 的次数排得更紧,就能看到不同的 CijC_{ij} 撞在同一个系数上。

继续追问#

  • 在卷积实验里把“循环长度”拖到 N=3N=3:为什么有些格子带着 ↺?它们对应多项式里哪一项被 x3=1x^3=1 折了回来?
  • 点值表示里,只取 2 个点时插值出的直线和真正的乘积在哪些地方一致?换成单位根,为什么得到的是 11+10x11+10x?
  • 条件数表里,等距实数点到 16 个时条件数约为 4×1094\times10^9。若矩阵固定,点值向量的 2 范数相对误差是 10−1210^{-12},条件数给出的最坏误差上界是多少?它能保证每个系数都损失这么多位吗?
  • 单位根实验里,取 N=12N=12、r=4r=4,路径为什么只走过 3 个不同的点?
  • 频率探针里,把信号频率设成 3、探针设成 13,和不为零。这是为什么?换成相位 90° 呢?
  • 打开“频率再加半圈”,信号频率是 3.5。为什么探针 3 和 4 都只收到一部分,连探针 10 也不为零?
  • FFT 里输入“平移冲激 δ₁”,输出全是单位根。它和循环矩阵实验里的“移位 PP”是什么关系?
  • NTT 的结果和真实系数不同的位置,差值是不是都是 17 的倍数?要让结果完全正确,模数至少要多大?
  • 矩阵编码里,列间隔为什么至少是 4?间隔 3 时具体是哪一个交叉项闯进了 C21C_{21}?
  • Strassen 的 7 个乘积里交换了 aa 与 ee 的乘法顺序吗?如果用到了交换律,还能把数字换成矩阵块吗?Karatsuba 呢?