动机
直接计算两个多项式的乘积,需要计算每一对系数的乘积。求值提供了另一种思路:在足够多的点上分别计算两个多项式的值,把得到的值逐点相乘,再做插值。当求值点具有足够的对称性、可以重复利用已有计算时,这种方法才会变得快速。
单位根恰好提供了这种对称性。它们的偶次幂与奇次幂把规模为 的变换与两个规模为 的变换联系起来。我们将推导这一基二快速傅里叶(Fourier)变换,证明它的逆变换公式,并解释为什么多项式乘法需要补零以避免回绕。
定义
定义 1.7.1
(离散傅里叶变换)
设 ,其中 为整数,并令 。对复向量 ,其离散傅里叶变换定义为
符号约定是定义的一部分,整个计算过程中必须前后一致。逆变换使用相反的指数。我们把精确的复数加法与乘法各算作一次单位运算,并假定所需的单位根均已给出。这是代数运算次数的计数,并不保证浮点计算或任意精度的位运算只需常数时间。
定理
定理 1.7.2
(基二变换)
对 ,通过对偶数下标与奇数下标的系数递归地做变换,离散傅里叶变换可以用 次复数算术运算计算出来。
定理 1.7.3
(逆变换与卷积)
逆变换公式为
如果把两个有限系数序列补零到某个 2 的幂长度,且该长度不小于它们的普通卷积的长度,那么对它们的离散傅里叶变换做逐点乘法,再做逆变换,就得到它们的普通卷积。
证明
拆分偶数与奇数下标
证明
(偶奇拆分与蝶形运算)
对 ,把变换写成
由于 ,这两个和分别是偶数下标向量与奇数下标向量的长度为 的离散傅里叶变换。把它们在 处的值记为 与 。又因为 ,且较短的变换以 为周期重复,所以
这样成对的更新称为蝶形运算。每一对都两次使用同一个乘积 。当 时,变换就是 。
设 为算术运算次数,则递归拆分给出 ,且 。在每一层递归深度上,各子问题的长度之和为 ,而非平凡的层数为 。因此总代价为 。预先计算所有需要的单位根,或以一致的方式生成它们,都可以计入这一运算次数;数值精度则是另一个独立的问题。
证明透视
为什么同样两个较小的变换能给出前后两半输出
对长度为 的单位根取平方,得到长度为 的单位根。把输出下标平移 ,较小的变换保持不变,但奇数部分的贡献变号。因此一对较小变换的值可以提供两个输出。
证明逆变换
证明
(以单位根的正交性证明逆变换)
关键恒等式是
其中 。若 ,则公比 是非平凡的 次单位根,其等比数列之和为 。若 ,则每一项都等于 。
把正变换代入所提出的逆变换公式,并交换有限和的次序。对于除 以外的每个输入下标,内层和都为零;在下标 处,内层和等于 ;除以 后恰好剩下 。逆变换同样可以使用相同的基二递归,只需改用 ,最后把所有输出乘以 。
这一证明也涵盖 的情形:此时唯一的单位根之和为 ,逆变换返回唯一的输入。它还说明了为什么在某种约定下改变符号,就必须相应地一致修改逆变换。连续两次应用正变换,而不做适当的反转与缩放,一般并不是逆变换。
概念视角代数
把变换看成矩阵,把卷积看成对角化
设 为矩阵,其元素为 ,则 。反演恒等式说明 ,因此 。循环卷积 就是用循环矩阵 去乘 ;卷积定理恰好说明 :每个循环矩阵在傅里叶基下都是对角的,其特征值就是第一列的变换。
求值与唯一性
把向量 与多项式 对应起来。正变换恰好就是在 个根 处对 求值。
命题 1.7.4
(单位根处的取值决定系数)
设 、 为次数小于 的复系数多项式。若对所有 都有 ,则 。
证明
(在互不相同的点上求值决定低次多项式)
这些点两两不同。若两个次数小于 的多项式在所有这些点上取值相同,则它们的差至少有 个不同的根。次数至多为 的非零多项式不可能有这么多根,所以差必为零。因此这些值唯一地确定系数向量。
零多项式是唯一在这 个根处的取值都为零、且次数小于 的多项式。用线性代数的语言说,求值映射是两个 维复向量空间之间的单射,因而是双射;前面给出的逆变换公式把这个双射显式地写了出来。这种唯一性解释了为什么只要变换长度足够大,就可以先求值、再把值相乘、最后插值来恢复乘积。但它本身并不能给出快速算法:在 个任意点上直接求值可能需要平方量级的工作量,一般的插值也是如此。蝶形递归与单位根求和形式的逆变换,利用的正是这些特殊的求值点。
对于实的输入值,当 时有 ,其中下标按模 理解。这是因为 ,并且共轭对有限和是可分配的。它可以用来检验计算出的变换,但不能代替逆变换的证明。当输入为复数时,这种共轭对称性不一定成立。
跟踪一次递归
在第一层,算法按下标的奇偶性把下标分开。在下一层,每个子问题又把各自的偶数位置与奇数位置分开。如此继续,直到得到只有一个元素的向量。递归实现可以返回每个较短的变换,并立即与其同层的另一半合并;它不需要独立地计算每个输出。
对 ,第一次拆分使用原始位置 与 。偶数一半接着拆分为 与 ,奇数一半拆分为 与 。在所有子问题中,每一层都涵盖全部八个系数位置。在这种递归视角下,叶子的排列顺序与通常的数值下标顺序不同;迭代式的原地实现往往要重新排列数据来适应这种顺序。数学上的递推式并不依赖于某种特定的原地置换。
上述运行时间界给出的是该算法运算次数的上界。它并不证明在每一种计算模型下,所有可能的方法都需要 次运算;也不断言在固定字长的机器上存在使用精确复数运算的实现。这些都是与代数恒等式相互独立的问题。
卷积与补零
定义 1.7.5
(循环卷积)
对长度为 的向量,循环卷积定义为
证明
(卷积定理与补零)
它的离散傅里叶变换是逐点乘积 。事实上,把卷积代入变换,交换有限和的次序,并令 。指数分解为 对应的因子与 对应的因子;由于 ,下标按模 约化不改变幂的值。这两个因子恰好就是 与 。
对普通多项式 与 ,它们的乘积的系数为 ,其中 。选取一个 2 的幂 ,并把两个向量都补零到长度 。普通乘积中没有任何非零系数的下标不小于 ,所以按模 约化下标不会产生回绕。对逐点乘积做逆变换,得到全部普通系数,后面跟着若干补零。
对于非空的输入序列,满足条件的最小的 2 的幂小于 的两倍。因此三次快速傅里叶变换加上 次逐点乘法,共使用 次复数运算。空多项式可作为零多项式单独处理。
反例模式
补零不足会改变乘积
取系数向量 与 ,但使用长度为二的循环变换。它们的普通卷积是 ,而循环回绕会把最后一个系数加到第一个系数上,得到 。在长度为二时做逐点乘法,计算出的是循环结果,而不是三个普通系数。
区分循环乘积与普通乘积
长度为 的循环卷积把相差 的倍数的位置视为同一个位置。例如,普通次数为 的项会贡献到循环位置二。用多项式的语言说,这是模 的乘法。离散傅里叶变换对这种循环乘积是完全正确的,因为每个求值点都满足 ;在这些点上的取值无法区分 与 。
对于单个普通乘积,补零可以避免这种歧义。如果最高可能的次数至多为 ,就没有系数会回绕。取下一个 2 的幂,既支持基二递归,又保持这一不等式成立。复杂度界中的输入长度指的是系数个数,包括显式给出的末尾零;去掉已知的末尾零是可选的预处理步骤。
因此,一个具体的乘法流程包含四步:选取满足次数界的 2 的幂长度,对两个输入补零,对两个补零后的向量做变换,再对逐点乘积做逆变换。逆变换返回的是该完整长度的向量;其中只有前 项才可能是普通乘积中的非零系数。在实现之前写清楚这些长度,可以避免意外丢失最高次项。
对于整数系数,人们可能希望先计算近似的复数逆变换,再把每个结果舍入到最近的整数。只有在证明了每个系数的误差都严格小于二分之一之后,这样的舍入才是合理的。精确算术下的定理并没有提供这样的数值误差界。精心选择的有限域变换与重构方法可以避开某些浮点问题,但模数必须含有合适的单位根且足够大,否则需要组合多个模数。这些进一步的条件不在本文的证明范围之内。
例题详解
例题 1.7.6
(四点变换)
对 ,有 。直接代入得到 。第一个输出是各项之和;由于输入为实数,第二个与第四个输出互为共轭。
例题 1.7.7
(一层蝶形运算)
对同一个输入,偶数向量 的两点变换为 ,奇数向量 的变换为 。对 ,蝶形运算给出 与 。对 ,乘以 后得到 与 。
例题 1.7.8
(多项式的平方)
多项式 的系数向量为 。在变换之前,把 补零为 。它的离散傅里叶变换为 ;逐点平方后再做逆变换,得到 。最后的零是补零,而不是额外的非零系数。
例题 1.7.9
(一点的情形)
当 时,离散傅里叶变换与其逆变换都返回输入值。两个常数多项式相乘只需要一次逐点乘法,不需要蝶形运算,也不需要非平凡的单位根。
常见错误
常见错误
(混用符号约定)
快速傅里叶变换是计算指定的离散傅里叶变换的算法;变换本身是一个线性映射。正变换的指数采用相反的符号,只有在逆变换与例子也相应调整的前提下,才是一种有效的替代约定。
常见错误
(只补零到较长输入的长度)
逐点乘法对应的是变换长度下的循环卷积。普通多项式乘法需要足够的补零,以防止下标不小于 的系数回绕到较低的位置。仅仅补零到较长输入的长度,并不总是足够。
常见错误
(把浮点快速傅里叶变换当作精确)
精确的代数证明并不会自动让浮点实现变得精确。舍入误差会影响系数,而把数值结果舍入到最近的整数,需要另外证明误差界。有限域上的数论变换同样需要合适的单位根,以及它自身的算术假设。
总结
基二快速傅里叶变换把离散傅里叶变换拆分为偶数与奇数两个子变换,并用蝶形运算把它们合并。单位根的正交性证明了逆变换公式。变换把循环卷积变成逐点乘法,而足够的补零使它能在所述的复数运算次数界内计算普通的多项式乘积。
练习
快速检查
(在所述的符号约定下,计算 的两点离散傅里叶变换。)
先求出 。
解答 · 答案
由于 ,变换为 。
快速检查
(对 ,计算四点离散傅里叶变换的第一项与第三项 。)
用 ,留意出现的是哪些幂。
解答 · 答案
,,因为 。
快速检查
(为什么用长度为二的循环变换去乘两个长度为二的系数向量,一般无法恢复全部三个普通系数?)
的系数去了哪里?
解答 · 答案
普通卷积在下标二处可能有非零系数。长度为二的循环卷积把下标二与下标零等同起来,把该系数加到第一项上。补零到不小于三的长度,就可以防止这种回绕。
快速检查
(解释为什么逆变换要除以 。)
把正变换代入逆变换公式。
解答 · 答案
单位根之和在输入下标与输出下标不相等时为零,相等时等于 。因此,把正变换代入逆变换后得到的是 ;除以 即恢复 。