动机
若将第一个多项式的每个系数与第二个多项式的每个系数两两配对相乘,则系数乘法的次数可能是平方量级。求值给出了另一条思路:在相同的点上对两个多项式求值,把函数值相乘,再恢复乘积的系数。
离散傅里叶(Fourier)变换选取单位根作为这些点。单位根的对称性使偶数项系数与奇数项系数可以共享规模更小的求值。我们将证明逆变换以及递归蝶形计算,并区分两种情形:一是带有循环回绕的模乘法,二是经过足够补零后得到的普通多项式乘积。
定义
设 N=2h,其中 h≥0 为整数,并令 ω=e2πi/N。对复向量 a=(a0,…,aN−1),其离散傅里叶变换定义为
ak=j=0∑N−1ajωjk(0≤k<N).正向变换采用正指数。逆变换将采用负指数,并带有因子 1/N。当 N=1 时取 ω=1,此时变换即恒等变换。
下文的运算次数把一次复数加法、复数乘法,或除以已知的非零整数 N 的除法都视为单位代价的精确运算,所需的单位根按规定可直接获得或生成。这一代数模型本身并不能界定浮点误差或比特复杂度。
对于正长度 r,s 的系数列表 a0,…,ar−1 与 b0,…,bs−1,它们的普通卷积定义为
ct=i+j=t∑aibj(0≤t≤r+s−2),
其中下标超出相应列表范围的项一律省略。对应的乘积多项式为 (i∑aizi)(j∑bjzj)=t∑ctzt。输入系数的首项或末项可以为零;决定安全输出范围的是所给出的列表长度,而不是假定的多项式次数。
定理/命题
对上述变换,
aj=N1k=0∑N−1akω−jk(0≤j<N).它可以通过递归在 O(Nlog(N+1)) 次精确复数运算内计算。逆变换同样适用该界,只需使用倒数根,并在最后乘以 1/N 进行缩放。
若两个长度为 N 的向量的变换分别为 a,b,则对逐点乘积 akbk 作逆变换,得到它们的循环卷积
dt=0≤i,j<Ni+j≡t(modN)∑aibj.要计算长度分别为 r,s 的两个列表的普通卷积,选取 2 的幂 N≥r+s−1,把两个列表都用零补到长度 N,然后作变换、逐点相乘、再求逆。前 r+s−1 个输出恰为普通卷积的系数;在精确算术下,其余输出为零。
证明思路
单位根求和使逆变换成立
对任意整数 q,等比级数恒等式给出
k=0∑N−1ωqk={N,0,N∣q,N∤q.若 N∤q,则公比 ωq 不等于 1,而其 N 次幂等于 1。若 N∣q,则每一项都等于 1。当 N=1 时该恒等式同样成立,因为此时每个整数都能被 1 整除。
把正向变换代入所提出的逆变换,并交换有限和的次序。恢复出的第 j 个分量中 at 的系数为
N1k=0∑N−1ω(t−j)k,对 0≤t,j<N,当 t=j 时它等于 1,否则等于 0。因此逆变换公式恢复了每一个输入。特别地,该变换是单射:没有两个不同的长度为 N 的系数向量具有相同的变换。
一次蝶形运算合并两个更小的变换
对 N≥2,把输入多项式拆分为偶次系数部分与奇次系数部分:
A(z)=E(z2)+zO(z2),E(y)=j=0∑N/2−1a2jyj,O(y)=j=0∑N/2−1a2j+1yj.数 ω2 是 (N/2) 次本原单位根。递归地计算长度为 N/2 的变换 Ek=E(ω2k) 与 Ok=O(ω2k)。对 0≤k<N/2,一次蝶形运算得到的两个值为
ak=Ek+ωkOk,ak+N/2=Ek−ωkOk,这是因为 ωN/2=−1,且这两个点的平方相同。当 N=1 时直接返回唯一的系数。对 h 作归纳即可证明,这些蝶形运算恰好按所述的输出顺序计算出所给的变换。
在每一递归层,所有子问题合计共有 N/2 个蝶形运算。每个蝶形运算使用一次旋转因子乘法以及两次加法或减法,所以当 N≥2 时,旋转因子乘法至多 (N/2)log2N 次,加减法至多 Nlog2N 次。每一层的单位根可以通过反复乘以该层的本原根来生成,每层只需线性的额外工作量;或者也可以由预先给定的表提供。逆变换使用相同的构造,只是把 ω 换成 ω−1,然后对 N 个输出作缩放。这就给出了所述的渐近界,其中也包含常数规模的 N=1 情形。
证明透视
相同的平方给出一对求值
两点 ωk 与 −ωk 的平方相同。因此,一次递归的偶部求值与一次递归的奇部求值就能产生两个输出,第二个组合只需改变符号。递归作用于系数,而不是对完整问题做两份互不相关的拷贝。拆分这一步要求每一层的 N 都是偶数,这就是变换长度取 2 的幂的原因;到了 N=1 便无可再拆,递归终止。
逐点乘积使指数按模 N 回绕
设 A(z)=i=0∑N−1aizi,B(z)=j=0∑N−1bjzj。在变换所用的点上,A(ωk)B(ωk) 就是两个变换后向量的逐点乘积。展开并应用逆变换,得到
N1k=0∑N−1ω−tki,j∑aibjω(i+j)k=i,ji+j≡t(modN)∑aibj.单位根求和消去了所有指数模 N 不与 t 同余的项。因此自然得到的输出是循环的:相差 N 的指数贡献到同一个系数上。等价地,它是乘积模 zN−1 的约化结果。
对于原始列表,有 0≤i+j≤r+s−2。若 N≥r+s−1,则该范围严格小于 N,所以任意两个可能的指数都不会回绕到同一位置。每个位置上的循环系数就是对应的普通系数;小于 N 的所有更高位置则不接收任何项。满足该不等式的最小 2 的幂小于 2(r+s−1),除非 r+s−1 等于 1,此时 N=1。因此,两次正向变换、N 次逐点乘法与一次逆变换共使用 O((r+s)log(r+s+1)) 次精确复数运算。
概念视角代数
商环中的逐点乘法
循环乘积就是环 C[z]/(zN−1) 中的乘法。由于 zN−1=k=0∏N−1(z−ωk) 有 N 个互异的根,根据中国剩余定理,在这些根处求值是一个环同构,映到带逐分量乘法的 CN。变换就是用系数坐标写出的这个同构,而逐点乘法就是右边那个环的乘法。
例题
计算 (1+2z) 与 (3+4z) 的乘积。把两个系数列表都补零到长度 4,并取 ω=i。它们的变换分别为
(3,1+2i,−1,1−2i),(7,3+4i,−1,3−4i).逐点相乘得到 (21,−5+10i,1,−5−10i)。再作逆变换得到 (3,10,8,0),所以乘积为 3+10z+8z2。这里 N=4≥2+2−1,最后的零是补零位置。
使用相同的输入,但在长度 2 下作变换。普通乘积的系数为 (3,10,8)。模 z2−1 时,8z2 一项变成常数项,得到循环输出 (11,10)。这一计算作为循环卷积是正确的,但并未返回普通的三系数列表。
常数列表 (7) 与 (−2) 的乘积满足 r+s−1=1。取 N=1:两个变换与逆变换都是恒等变换,唯一的逐点乘积为 −14。这里既不需要蝶形运算,也不需要非平凡的本原根,更不需要除以更大的变换长度。
输入与输出规模为何重要
补零条件是对给定列表长度下所有系数取值而言的充分的最坏情形条件。若 N<r+s−1,则如例题所示可能发生回绕,但这并不一定改变每一个具体的答案:某些高次系数可能为零或相互抵消。反过来,仅仅观察到某一个输出位置为零,并不能证明其他位置没有发生回绕。
变换方法产生的是整个系数列表。若只需要某一个系数,直接对其合格的项求和可能比计算整个变换更省。若列表中含有大量零,稀疏表示或其他乘法方法也可能有用。这些替代方案对应不同的输入与运算模型;变换的复杂度界并不声称它对每个实例都是最优的。
相关等于反转其中一个列表后的卷积
设 x 的长度为 r,y 的长度为 s。对整数位移 τ,定义有限互相关
R(τ)=0≤i<r0≤i−τ<s∑xiyi−τ.
通过令 yj=ys−1−j(0≤j<s)来反转并取共轭第二个列表。若 c 是 x 与 y 的普通卷积,则
R(τ)=cτ+s−1(−(s−1)≤τ≤r−1).
事实上,卷积下标方程 i+j=τ+s−1 给出 s−1−j=i−τ。在两个和式中,位于两个列表之外的项都被省略。因此,相同的补零规则可以计算所有这些位移对应的值,但必须把输出位置平移回去 s−1;输出位置本身并不是带符号的位移。
例如,设 x=(1,2,0),y=(2,1)。反转后的列表为 (1,2),它与 x 的普通卷积为 (1,4,4,0)。各项分别对应位移 −1,0,1,2。在位移为零处,值 4 即 1⋅2+2⋅1。对于实数列表,只反转而不取共轭已经足够,但对于真正的复数数据,这会改变定义。
范数恒等式提供另一种检验
同样的单位根求和可以证明此约定下的有限 Parseval 恒等式:
k=0∑N−1∣ak∣2=Nj=0∑N−1∣aj∣2.
展开模的平方,交换有限和的次序,并对每一对系数下标使用单位根求和,只有下标相等的项得以保留。因子 N 与未缩放的正向变换相联系;若约定对正向变换作缩放,则该因子会随之改变。与该恒等式吻合只是一项必要的一致性检验,并不能证明变换的每个分量都正确。
整数答案与近似算术
当两个输入列表都由整数构成时,每个普通卷积系数都是整数。设某个实现给出实数 ct,并且另有独立确立的保证
∣ct−ct∣<21对每个输出下标 t 成立.
那么把每个 ct 四舍五入到最近的整数,就能返回精确的系数。严格不等式避免了落在两个整数正中间的平局情形。若逆变换计算产生的是复数近似值,则只要每个实部的误差小于二分之一,就足以完成这一舍入步骤。
变换恒等式本身并不提供这样的数值保证。近似的单位根、算术舍入、溢出以及系数大小,都必须通过单独的误差分析来控制。同样,精确复数运算的次数也不意味着任意大的整数可以在常数比特时间内相乘。带有已证明重构界的模变换是另一种精确方法,但它需要自己的模数与单位根假设。
共轭对称性与验证检查
若输入系数为实数,则取复共轭给出:对 1≤k<N,有 aN−k=ak。该等式由 ω=ω−1 与 ωN=1 推出。特别地,当变换长度为偶数时,下标为零与 N/2 的分量是实数。这一对称性有助于检查所算出的变换,但它本身并不能保证每个输出系数及其舍入误差都正确。
对于所提出的乘积列表,在任意选定的点上求值会给出一个必要恒等式:所报告的乘积在该点的值必须等于两个输入在该点的值之积。仅凭一个点并不能对任意多项式给出确定性的相等性证明,因为两个不同的多项式可能在该点取值相同。比较每一个系数,或者在已知次数界的前提下使用足够多个互不相同的求值点,则可得到完整的精确检验。
反例模式
单点求值不能验证全部系数
在 z=1 处,多项式 1 与 z 的值都是 1,但它们的系数列表并不相同。单点上的一致可以发现某些错误,也会漏掉另一些错误。逆变换之所以成功,是因为它使用了全部 N 个单位根以及单位根求和恒等式,而不是因为某一次求值碰巧一致。
常见错误
把正向变换连续做两次,并不会还原输入。由于 k∑akωjk=t∑atk∑ω(t+j)k,单位根求和给出 Na(−j)modN。取 a=(1,2,0,0)、N=4,其变换为 (3,1+2i,−1,1−2i);以 ω=i 再变换一次,得 (4,0,0,8)=4(a0,a3,a2,a1):各项次序反转,并被放大 N 倍。逆变换必须使用 ω−1 及因子 1/N。
若取 N≥max(r,s) 而不是 N≥r+s−1,指数就会回绕。以 (1+z+z2)(1+z+z2+z3)=1+2z+3z2+3z3+2z4+z5 为例,取 N=4 得到循环乘积 (3,3,3,3),因为 z4、z5 折回 z0、z1。取 N=8 则得 (1,2,3,3,2,1,0,0)。
上述恒等式是关于复数的精确陈述。浮点运算只给出近似值;只有另有论证表明每个误差都小于二分之一时,取整成整数才站得住脚。没有这个误差界,即使代数推导正确,取整后的输出也可能是错误的整数。
总结
单位根给出了一个可逆的求值映射。偶奇拆分通过蝶形递推,以 O(Nlog(N+1)) 次精确复数运算计算该映射。逐点乘积给出循环卷积;长度至少为 r+s−1 即可避免指数回绕,并返回普通多项式的系数。精确运算次数、比特复杂度以及数值舍入保证是彼此独立的论断。
练习
快速检查
(按照所述的正指数约定,计算 (a0,a1) 的长度为 2 的变换。)
解答 · 答案
此时单位根为 ω=−1,所以变换为 (a0+a1,a0−a1)。逆变换使用相同的两个和,再除以 2。
快速检查
(对于长度分别为 3 和 4 的两个列表,若必须取 2 的幂并使用所述的补零规则,应选择多大的变换长度?)
解答 · 答案
普通乘积至多有 3+4−1=6 个系数位置。不小于 6 的最小的 2 的幂是 8。
快速检查
(求 (1,1) 与自身的长度为 2 的循环卷积,并将其与普通卷积比较。)
解答 · 答案
普通卷积为 (1,2,1)。常数项与二次项系数会回绕到一起,在长度 2 下得到循环输出 (2,2)。
快速检查
(为什么实部的绝对误差小于二分之一可以证明对整数系数作舍入是合理的,而误差恰好等于二分之一则不一定?)
解答 · 答案
以整数为中心、半径为二分之一的开区间不含其他整数,也不会触及中点。当误差恰好为二分之一时,近似值可能恰好落在两个整数正中间,此时舍入取决于平局规则,不一定返回所需的那个整数。