从卷积到 FFT
十二个可以拖动的实验:卷积的乘积表、点值与单位根、复数旋转、欧拉级数、频率探针、FFT 蝶形与完整算例、NTT、循环矩阵的对角化、Karatsuba、Strassen 和矩阵编码。
此刻听到的,是过去每一刻留下的余音
用“演奏家、音乐厅、听众”三个角色看卷积:演奏家视角里,每一拍输入 在 响起后向右拖出按 衰减的余音,此刻听到的总声 就是所有未散尽余音的垂直叠加;听众视角里,固定此刻 往过去回看,时间差 让响应 翻转并平移,重叠处相乘再相加(即乘积表的斜线 )。切换到连续小提琴,可以看到连续信号 切成薄片 后如何收敛到卷积积分 。
柱子按来源分色:颜色 i 是第 i 个输入拖出的余音。选中列的色块,就是左边表里高亮的那条斜线。
普通卷积的长度是 3+4−1=6。把下面的 N 拉到 6 或更大,循环卷积就和它完全一样;小于 6 时,末尾的项会绕回开头。
同一个多项式的两种描述:系数和点值
次数小于 的多项式由 个互不相同点上的值唯一确定。在点值表示下,乘法只是把同一点上的两个值相乘。 的次数是 2,需要 3 个点才能插值回来。把求值点换成单位根,求值就是 DFT,插值就是逆 DFT。下方的条件数表说明单位根还有一个好处:固定矩阵时,2 范数相对误差的条件数为 1;实际计算仍会舍入。
A=1+2xB=3+4xC=AB
| −1.5 | −2 | −3 | 6 |
| −0.5 | 0 | 1 | 0 |
| 0.5 | 2 | 5 | 10 |
点值表示下,乘法只是把同一行的两个数相乘,3 个点就做 3 次乘法。C 的次数是 2,3 个点已经够用;多出来的点只是重复确认同一个多项式。
插值有多稳:范德蒙德矩阵的条件数
| 点数 n | 本图的实数点 | 单位根 | |
|---|---|---|---|
| 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 |
从点值解出系数,就是解方程 ,其中 。固定精确的 V、仅扰动右端点值时,系数向量在 2 范数下的相对误差至多是点值相对误差的 倍。这里的条件数描述最坏方向的敏感性,不表示每组数据都会损失对应位数,也不保证每个系数的相对误差。
单位根的 V 是傅里叶矩阵 F,满足 ,因此 是酉矩阵且 :上述范数相对误差不会因这个线性问题被放大。计算单位根、执行变换与逐点乘法仍有浮点舍入误差;大条件数的表值本身也只是双精度估计。现在的 3 个实数点,估计条件数为 5.6。
乘一个复数,就是把整个平面转一下、放缩一下
乘上 ,长度相乘、角度相加:。拖动 和 ,看单位方格怎样被整体旋转和缩放。连按“z ← zw”,点就在一圈圈地转:复数把“旋转”变成了乘法,后面的单位根和傅里叶都靠这一点。
淡色的单位方格和字母 F 是原图;实线是它们乘以 z 之后的样子。整个平面被同一个复数旋转并缩放,方格依旧是方格:乘法不会把平面拉歪。
指数级数为什么会绕成一个圆
。每一项是上一项乘 :乘 转 90°,乘 改变长度。前几项可能越来越长,但阶乘最终压过 ,折线一边左转一边收缩,停在单位圆上角度为 的点。下方的对数柱图显示各项长度在 处最大,较大的项相消会增加舍入风险,有限项截断则是另一种误差。
- 实方向 +1,长 1
- 虚方向 +i,长 3.142
- 实方向 −1,长 4.935
- 虚方向 −i,长 5.168
- 实方向 +1,长 4.059
- 虚方向 +i,长 2.55
每一项都是上一项乘以 :先转 90°,再按 缩放。本实验取 θ≥0,非零项依次向左转;随着项数充分增加,部分和趋向单位圆上角度为 θ 的点。项数有限时,终点可能仍离它很远。实部方向的项(偶数项)拼出 cos θ,虚部方向的项(奇数项)拼出 sin θ。
柱高是第 n 项的长度 (对数刻度, 以下截平),蓝色是已经加上的项。相邻两项之比是 :比值大于 1 时项还在变长,小于 1 后开始缩短。橙色标出最长项之一,第 3 项,长 5.17;画出的 30 项部分和离原点最远时是 5.04。
上方误差比较的是当前有限项和与 sin、cos 算出的目标,包含级数截断与浮点舍入两种影响。较大的中间数相消会增加舍入风险,但最长项不能直接给出误差或可信位数。本实验最多相加 30 项,θ 较大时截断误差仍可能很大;继续增加项数与控制浮点误差是两个问题。
转完整数圈,箭头首尾相接回到起点
每次转 圈。把 首尾相接:只要 ,折线就会闭合,和为 0; 时每一项都是 1,和为 。逆 DFT 和卷积定理的证明都只用到这一个恒等式。把所有 的和排成矩阵,就是 。
。ω^1 是转 1/8 圈的旋转。走 8 步回到起点,折线是一个正 8 边形;闭合的折线首尾重合,和为 0。 虚线连着 ω⁰ 和 ω^4:,相对的两个根互为相反数,FFT 正是靠这一点把计算对半分。
同一个和,拼成矩阵:
傅里叶矩阵 。 的第 格是 ,正好是右上图 时的和:只有对角线上 时为 8,其余都是 0。高亮的是 的那条斜线,点任意一格可以换成那一格的 r。于是 :逆变换只要把 ω 换成 ,再除以 N,不需要另解方程。
用反向旋转去“抵消”信号中的某个频率
:把第 个采样乘以 ,也就是转 圈,再首尾相接。对于单个整数频率的复指数,匹配的探针让它停止旋转,其余探针累加为 0。本实验使用实余弦,包含正、负两个方向的分量,需要分别考虑。实信号的频率 同时出现在镜像位置 。信号频率超过 8 时,16 个采样已经分不清它和更低的频率;“频率再加半圈”让信号落在两个探针之间,通常会在多个频点出现泄漏分量。
箭头首尾相接围成闭合多边形,总和回到原点:这个频率转完整数圈,方向彼此抵消,信号里没有它。
一对求值点共享一次计算
。 和 互为相反数,平方相同,所以两处的 是同一个值,只差 前面的符号:。右边的圆显示这一点: 个单位根平方后两两重合,问题规模减半,一共 层。可以改 、自己输入序列,点任意一个蝶形看它的两个输入和两个输出。
点“下一层”开始合并。每一层都可以点击右侧一列的某个节点,查看算出它的那次蝶形。
- 直接按定义
- 64 次复数乘法
- FFT 已用
- 0 / 12 次蝶形
补零、变换、相乘、逆变换,一步一步算完
用 FFT 乘多项式分六步:补零到足够长,分别变换两个系数序列,逐点相乘,逆变换,最后读出整数。复数版本有浮点误差,只有实部误差小于 1/2 时,取整才保证恢复整数;NTT 在模 的整数里做同样的事,没有误差,但只能得到余数。换成“大系数”可以看到:结果超过 时需要更大的素数,或用几个素数的余数经中国剩余定理拼回来。
- 补零
- 变换 a
- 变换 b
- 逐点相乘
- 逆变换
- 读出结果
| 0 | 1 | 3 | · | · | · | · | · |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 4 | · | · | · | · | · |
| 2 | 0 | 0 | · | · | · | · | · |
| 3 | 0 | 0 | · | · | · | · | · |
每一步都在表里新增一列。灰色的列还没有算到。
本面板实际调用与蝶形实验相同的基 2 FFT;逆变换使用共轭、正变换和除以 N。它展示的是这组输入的计算结果,不能作为所有 FFT 实现的误差界。
傅里叶变换对角化了什么
循环卷积写成矩阵 ,每一列是上一列循环下移一格,即 ,其中 是循环移位。傅里叶向量是 的特征向量(移一格只乘一个单位根),所以也是任何 的多项式的特征向量。换到这组基下,卷积变成了逐点乘法。去掉绕回项得到普通卷积的 Toeplitz 矩阵,它不再是对角的,要先补零嵌进更大的循环矩阵。
每一列都是上一列向下循环挪一格,所以 C_b = b₀I + b₁P + b₂P² + b₃P³。傅里叶向量是 P 的特征向量,于是也是 C_b 的特征向量:对角线上依次是 b 的 DFT,对角线外全是 0。
三次乘法换掉四次,交叉项从和里减出来
的中间项只需要 这个和。一次 同时算出四个格子,减去两个对角格就得到它。系数可以换成半长的多项式,于是 ,。
直接展开:四个格子,四次乘法
两个对角格是 和 。另外两个格子只需要它们的和, 把四个格子一起算出来,减去两个对角格就得到。
Karatsuba:三次乘法
同一件事:在 0、1、∞ 三个点求值再插值
指最高次系数。次数为 2 的乘积由 3 个点值确定,每个点值各要一次乘法,所以是 3 次。这正是“点值表示”实验的思路,只是点选得特别便宜。
把每个系数换成半长的多项式,递归 4 层(n = 16)
只数乘法: 对 ,剩 31.6%,指数从 2 降到 。每层还要做 次加减(两次求和、两次相减、拼接时的重叠相加)。下表把乘法和加法都算上(直接算法 次):
| n | 直接算法 | 递归到底 | 比值 | 最佳切换块 | 比值 |
|---|---|---|---|---|---|
| 2 | 1.40 | 不递归 | 1.00 | ||
| 4 | 1.32 | 不递归 | 1.00 | ||
| 8 | 1.12 | 4 | 0.91 | ||
| 16 | 0.92 | 4 | 0.77 | ||
| 32 | 0.73 | 4 | 0.62 | ||
| 64 | 0.57 | 4 | 0.49 | ||
| 128 | 0.44 | 4 | 0.38 | ||
| 256 | 0.34 | 4 | 0.29 | ||
| 512 | 0.26 | 4 | 0.22 | ||
| 1024 | 0.19 | 4 | 0.17 |
比值小于 1 才说明更省。“最佳切换块”指递归到这个大小就改用直接算法,取总次数最少的那个。递归到底在 n=16 才开始省;在长度 4 处切换,n=8 就能省约 9%,n=64 能省一半。
七次乘法换掉八次,递归之后指数下降
普通 矩阵乘法要 8 个乘积。Strassen 先做加减,造出 7 个乘积,再只靠加减拼回结果;多出来的项在拼接时互相抵消。因为整个过程没有用到乘法交换律,数字可以换成矩阵块,于是 ,。
M₁ 展开后落在哪些格子
| A 的元素 | e | f | g | h |
|---|---|---|---|---|
| a | +1 | +1 | ||
| b | ||||
| c | ||||
| d | +1 | +1 |
| A 的元素 | e | f | g | h |
|---|---|---|---|---|
| a | ||||
| b | ||||
| c | ||||
| d |
| A 的元素 | e | f | g | h |
|---|---|---|---|---|
| a | ||||
| b | ||||
| c | ||||
| d |
| A 的元素 | e | f | g | h |
|---|---|---|---|---|
| a | +1 | +1 | ||
| b | ||||
| c | ||||
| d | +1 | +1 |
每张表的第 行第 列是单项 (如 )在该输出里的系数,框出的是这个输出真正需要的两项。+1 和 −1 是这个乘积带进来的项,框外的必须由别的乘积抵消。
点开一个乘积
- C₁₁(系数 +1):提供 ae;+ah 被 −M₅ 抵消;+de 被 −M₄ 抵消;+dh 被 −M₇ 抵消
- C₂₂(系数 +1):提供 dh;+ae 被 −M₆ 抵消;+ah 被 −M₃ 抵消;+de 被 −M₂ 抵消
把数字换成矩阵块,递归 4 层(n = 16)
只数乘法: 对 ,剩 58.6%,指数从 3 降到 。但每层还要做 18 次块加减。下表把乘法和加法都算上(直接算法 次):
| n | 直接算法 | 递归到底 | 比值 | 最佳切换块 | 比值 |
|---|---|---|---|---|---|
| 2 | 2.08 | 不递归 | 1.00 | ||
| 4 | 2.21 | 不递归 | 1.00 | ||
| 8 | 2.10 | 不递归 | 1.00 | ||
| 16 | 1.92 | 8 | 0.99 | ||
| 32 | 1.73 | 8 | 0.93 | ||
| 64 | 1.54 | 8 | 0.84 | ||
| 128 | 1.36 | 8 | 0.75 | ||
| 256 | 1.19 | 8 | 0.66 | ||
| 512 | 1.05 | 8 | 0.58 | ||
| 1024 | 0.92 | 8 | 0.51 |
比值小于 1 才说明更省。“最佳切换块”指递归到这个大小就改用直接算法,取总次数最少的那个。递归到底要到 n=1024 才比直接算法少;在 8×8 处切换,n=64 就能省 16%。
把矩阵乘法塞进一次多项式乘法
把 、 的元素放到精心挑选的次数上,让 需要的两项恰好落在同一个次数,其他乘积落在别处。这样一次多项式乘法就算出了 ;代价是多项式长度涨到 ,大部分系数都是用不上的交叉项。切换 的次数安排,可以看到间隔太小时各个 怎样撞在一起。
的 16 个乘积,标出各自的次数
| b₂₁·x⁰ | b₁₁·x¹ | b₂₂·x⁴ | b₁₂·x⁵ | |
|---|---|---|---|---|
| a₁₁·x⁰ | x⁰7 | x¹5 | x⁴8 | x⁵6 |
| a₁₂·x¹ | x¹14 | x²10 | x⁵16 | x⁶12 |
| a₂₁·x² | x²21 | x³15 | x⁶24 | x⁷18 |
| a₂₂·x³ | x³28 | x⁴20 | x⁷32 | x⁸24 |
按次数合并,读出四个位置
,与直接计算一致。
每个 的两项落在同一个次数上,而且那一格没有别的乘积。间隔再小一点,就会有项撞到一起,可以切换试试。点击某一次的系数,左表中落到这一格的乘积会被标出;红框是 AB 需要、却没有单独落在一格里的乘积。
有用的系数只占一小部分
一般的编码需要 个系数位置,其中只有 个是 的元素。即使多项式乘法只需 ,这里的 也已经是 ,并不比直接计算更快。
阅读说明与延伸问题
这条线怎样连起来#
十二个实验按文章的顺序走完一条线:
- 卷积:输出的第 项收集所有 的乘积 。多项式乘法也是这样收集系数。拖动“循环长度”可以把下标改成按 取余,看补零和绕回的区别。打开“频域”,可以看到同一个结果在 DFT 之后变成逐点相乘。
- 点值表示:在 个点上求值,多项式乘法就变成逐点相乘。点数少于乘积的系数个数时,插值会得到另一个多项式。条件数表比较了实数点和单位根插值的数值稳定性。
- 复数乘法:长度相乘,角度相加,旋转因此可以写成乘法。
- 欧拉公式: 的级数每一项都比上一项多转 90°,部分和绕成螺旋,最后落在单位圆上。对数柱图标出最长的一项,帮助观察相消与舍入风险;有限项截断误差另外存在,不能由最长项直接推算。
- 单位根: 沿圆周跳动。只要 不是 的倍数,这些箭头首尾相接后回到原点,和为零。把这些和排成矩阵就是 。
- 频率探针:DFT 用反向旋转去比较信号。对单个整数频率的复指数,匹配频率时旋转被抵消,其余频点累加为零。本实验用实余弦,正负频率会形成一对共轭分量。余弦频率不是整数时,通常会出现多个频点的泄漏分量;还要考虑正负频率、相位和共轭对称。
- FFT: 与 的平方相同,一对输出共享一次计算,每一层把问题规模减半。
- 完整算例:补零、两次变换、逐点相乘、逆变换,一步一步算出 。切到 NTT,在模 的整数里重做一遍:模 17 时超过模数的系数会被折回,换更大的素数,或打开“大系数”用两个素数的余数经中国剩余定理拼回结果。
- 循环矩阵:循环卷积是移位算子 的多项式。傅里叶向量是 的特征向量,所以傅里叶变换把卷积矩阵变成对角矩阵。去掉绕回得到的 Toeplitz 矩阵不再能对角化,要先补零嵌进更大的循环矩阵。
- Karatsuba:两个一次多项式相乘本来要 4 次乘法,用 一次得到两个交叉项之和,只需 3 次。
- Strassen:一般矩阵没有循环结构,但可以先做加减,再用 7 个乘积代替 8 个,递归下去指数就降到 。
- 矩阵编码:把 矩阵的元素放到不同次数上,多项式乘积的四个系数恰好是 的四个元素。其余系数都是用不上的交叉项,这也是这种编码无法直接加速的原因。把 的次数排得更紧,就能看到不同的 撞在同一个系数上。
继续追问#
- 在卷积实验里把“循环长度”拖到 :为什么有些格子带着 ↺?它们对应多项式里哪一项被 折了回来?
- 点值表示里,只取 2 个点时插值出的直线和真正的乘积在哪些地方一致?换成单位根,为什么得到的是 ?
- 条件数表里,等距实数点到 16 个时条件数约为 。若矩阵固定,点值向量的 2 范数相对误差是 ,条件数给出的最坏误差上界是多少?它能保证每个系数都损失这么多位吗?
- 单位根实验里,取 、,路径为什么只走过 3 个不同的点?
- 频率探针里,把信号频率设成 3、探针设成 13,和不为零。这是为什么?换成相位 90° 呢?
- 打开“频率再加半圈”,信号频率是 3.5。为什么探针 3 和 4 都只收到一部分,连探针 10 也不为零?
- FFT 里输入“平移冲激 δ₁”,输出全是单位根。它和循环矩阵实验里的“移位 ”是什么关系?
- NTT 的结果和真实系数不同的位置,差值是不是都是 17 的倍数?要让结果完全正确,模数至少要多大?
- 矩阵编码里,列间隔为什么至少是 4?间隔 3 时具体是哪一个交叉项闯进了 ?
- Strassen 的 7 个乘积里交换了 与 的乘法顺序吗?如果用到了交换律,还能把数字换成矩阵块吗?Karatsuba 呢?