利用快速傅里叶变换(FFT)计算多项式乘法

1、利用快速傅里叶变换(FFT)计算多项式乘法作者:宋振华摘要本文将讨论快速傅里叶变换(FFT)，利用FFT设计一种算法，使多项式相乘的时间复杂度降低为0(nlog2n),以便在计算机上高效计算多项式乘法.关键词:快速傅里叶变换、多项式乘法目录一、引言二、算法概述三、引理1、多项式的表示系数表达形式点值表达形式插值2、利用离散傅里叶变换(DFT)与FFT导出结果的点值表达形式单位复数根离散傅里叶变换(DFT)通过快速傅里叶变换(FFT)计算向量y3、利用FFT计算逆DFT,将结果的点值表达形式化为系数表达形式在单位复数根处插值利用FFT计算逆DFT四、算法具体流程五、算法的实际应用:计算大整数乘法

2、六、参考文献、引言基于FFT的离散傅里叶变换(DFT)技术，是当今信息传输、频谱分析等领域中最重要的数学工具之一.在计算机编程中,我们经常需要计算两个多项式函数的乘积对于两个n次多项式函数，计算其乘积最直接方法所需时间为C2)本文将讨论快速傅里叶变换(FFT),利用FFT设计一种算法，使多项式相乘的时间复杂度降低为0(nlog2n),以便在计算机上高效执行.二、算法概述通过FFT进行离散傅里叶变换，将两个多项式由系数表达形式转化为点值表达形式.将这2个点值表达形式的多项式相乘，得到结果的点值表达形式.最后利用FFT做DFT的逆,得到结果的系数表达形式.三、引理1、多项式的表示系数表达对于次数为

3、n的多项式A(x)=Yaxi,其系数表达是一个由系数组成ii=0TOC o 1-5 h z HYPERLINK l bookmark6 o Current Document 的向量a=(a,aa01n考虑用系数形式表示、次数为n的多项式A(x)、B(x)的乘法运算.记C(x)=A(x)B(x)=艺cxi有c=ab.可以看出，采取逐个计iiji-ji=0j=0算c(0i2n,iGN)的方式进行求解，其时间复杂度为0(n2)i点值表达定义：一个次数为n的多项式A(x)的点值表达就是由一个有n个点值对组成的集合(x,y)10in,igN,y=A(x),使得对于k=0,1,2,.,n,所有iiii的x

4、各不相同.k点值表达下多项式乘法对于n次多项式A(x),B(x)，设其点值表达式分别为：A(x):(x,y),(x,y),(x,y)，,(x,y),001122nnB(x):(x,y,),(x,y，),(x,y,),.,(x,y,)001122nn设C(x)=A(x)B(x),由于C(x)的次数为2n,因此必须对A(x)和B(x)的点值表达式进行扩展,使每个多项式都包含2n+1个点值对.给定A,B的扩展点值表达:A(x):(x,y),(x,y),(x,y)，,(x,y),0011222n2nB(x):(x,y,),(x,y，),(x,y,),.,(x,y,).0011222n2n,yy,).2

5、n2n则C(x)的点值表达形式为：(x0，y0y0)，(I,人，(x2,y2打)，(x2n因此，计算C(x)点值表达式的时间复杂度为0(n).插值求值运算的逆(从一个多项式的点值表达形式确定其系数表达形式)称为插值下面将证明，n个点求值运算与插值运算是定义完备的互逆运算.a.多项式的点值表达可以唯一确定多项式的系数表达形式.多项式的点值表达等价于矩阵方程:卩xx2、xn(a)(y)000001xx2xnay111111xx2xna=y:22222Jxnx2nxn丿na丿ny丿n(3-1-3-a)记系数矩阵为V,由Vandermonde行列式可知，|V|=nC-x)ij0ijn而Vi,jgN,0

6、i,jn,i丰j，有x丰x，因此|V|丰0，即V可逆.ij因此对于给定点值表达,我们能够唯一确定系数表达式,且b.对于次数为n的多项式函数A(x),插值算法基于如下Lagrange公式:(3-1-3-b)n(x一x)A(xLZykn(x-x)k=0kjj丰k容易验证,Lagrange公式的计算复杂度为0(n2).i=0因此，n个点求值运算与插值运算是定义完备的互逆运算，它们将多项式的系数表达与点值表达进行相互转化.2、利用离散傅里叶变换(DFT)与FFT导出结果的点值表达形式(1)单位复数根n次单位复数根是满足On=1的复数O.n次单位复数根恰好有n个:对于k=0,1,.,n-1,这些根是en

7、.由Euler公式e二cos)+isin)可知，这n个单位复数根均匀地分布在以复平面原点为圆心的单位圆圆周2兀上.O二en称为主n次单位根，所有其他n次单位根都是o的幂次.nnn个n次单位复数根O0,O1,O2,.,On-1在乘法意义下构成一个群,nnnn该群与群同构由此，可以得到如下推论：nna.,2加k.2kVn0,k0,d0,有Odk=e加=eln=0k.dnn(3-2-1-a)Vn二2k,kgN*,O2=0=1.n2n若n=2k,kgN*,(0/)210in,igN=(0i)210i,igN.nn/22(3-2-1-c)(3-2-1-b)对推论c的证明:由a可知，VkGN,C)=Ok/

8、2nn/2所以对于kGN，ok2，有(Ok+n/2)2=O2k+n=O2kOn=O2k二(Ok)2.得证.nnnnnnd.VngN*,kgN且k不能被n整除，有艺O=0.ni=0(3-2-1-d)对推论d的证明:艺C)=(Ok)n1nOk-1i=0n(On)k-1(1)k-1Ok-1Ok-1nn离散傅里叶变换(DFT)对于n次多项式A(x)=工axi,ii=0其系数形式为a=(a,a,a)T.01n(3-2-2-1)(3-2-2-2)设y=A(Ok)=aOki,0kn,kGN,knin+1则向量y二(y,yy)T(3-2-2-3)01n就是系数向量a二(a,a，,a)t的离散傅里叶变换.01n

9、通过快速傅里叶变换(FFT)计算向量y.对于n次多项式A(x)=Yaxi,不妨假设n+1二2p,peN对于n+1ii=0不为2的整数次幂的情况类似,此处不再讨论.FFT采取了分治策略，采用A(x)中偶数下标与奇数下标的系数，分别定义两个新的次多项式：2Ab(x)=a+ax+ax2hfax2,(3231)024n-1Ali(x)=a+ax+ax2ffax2(3232)135n注意到Ab(x)包含A所有偶数下标的系数，Abl(x)包含A中所有奇数下标的系数，于是有：A(x)=Abl(x2)+xAi(x2).(3233)所以，求A(x)在W0,W1,Wn处的值的问题转化为：nf1nf1nf1求次数为

10、-的多项式A0(x),Ai(x)在点(W0)2,(Wi)2,2nf1nf1(Wn)2处的取值.nf1根据(2-2-3-3)综合结果.根据(2-2-1-c),式(2-2-3-3)不是由n+1个不同值组成,而是仅由凹个出次单位复数根所组成，每个根正好出现2次.因此，我们递归22地对次数为n的多项式A0(x),A1(x)在nF1个nF1次单位复数根处进行求值这些子问题与原始问题形式相同，但规模变为一半.下面确定DFT过程的时间复杂度.注意到除了递归调用外，每次调用需要枚举a=(a,a，,a)T中所有元素，将a划分为ab=a,a，a、01n02nat=a,a,a，,a,分别与多项式A0(x),Au(x

11、)相对应.其时间复杂135n-1度为0(n)因此,对运行时间有下列递推式:T(n)二2T(n)+0(n).(3-2-3-4)求解该递推式,有T(n)=0(nlogn).(3-2-3-5)2采取快速傅里叶变换，我们可以在0(nlogn)时间内，求出次数为n2的多项式在n+1次单位复数根处的值.3、利用FFT计算逆DFT将结果的点值表达形式化为系数表达形式(1)在单位复数根处插值n+1根据(2-1-3-a),我们可以把DFT写成矩阵乘积y=Va，其中V是nDn+1A。1yiy2Dn+1D2n+1D2n+1D4n+1Dnn+1D2nn+1(a10a1a2(3-3-1-1)CDnn+1D2nn+1CD

12、n2丿n+1易知Vp0.即V可逆.n+1n+1F面证明V-1(i,j)处元素vn+1ijD-ijn11.n+1(3-3-1-2)个由d适当幂次填充成的Vandermonde矩阵.考虑V-1V(i,j)处元素p:n+1n+1ijED-ik+1kjijn+1n+1k-0EDk(j-i)n+1n+1k-0(3-3-1-3)当j二i时,p二1；当j丰i时，根据(2-2-1-d)可知,p二0.ijij满足V-1Vn+1n+1n(3-3-1-4)给定逆矩阵V-1,可以求出a-(a,a，,a)T.n+101n(3-3-1-5)其中a-1yd-ki.in+1kn+1k-0(2)利用FFT计算逆DFT比较(3-

13、3-1-5)和(3-2-2-2)可知,对FFT算法进行如下修改,即可计算出逆DFT:把a与y互换，用o-i替换，并且将计算结果每个元素除以n.因此，我们也可以在0(nlogn)时间内计算出逆DFT.2四、算法具体流程1、加倍多项式次数通过加入n个系数为0的高阶项，把多项式A(x)和B(x)变为次数为2n的多项式，并构造其系数表达.2、求值通过应用2(n+1)阶的FFT计算出A(x)和B(x)长度为2(n+1)的点值表达.这些点值表达中包含了两个多项式在2(n+1)次单位根处的取值.3、逐点相乘把A(x)的值与B(x)的值逐点相乘,可以计算出C(x)二A(x)B(x)的点值表达，这个表示中包含了

14、C(x)在每个2(n+1)次单位根处的值.4、插值通过对2(n+1)个点值应用FFT，计算其逆DFT，就可以构造出多项式C(x)的系数表达.由于1、3的时间复杂度为0(n),2、4的时间复杂度为0(nlogn)，2因此整个算法的时间复杂度为0(nlogn).2五、算法的实际应用:计算大整数乘法在密码学等领域中，经常需要进行大整数乘法运算.如果对整数p,q逐位相乘然后相加，其时间复杂度为0(logpJog。q).当p,q规模巨大时,这种算法将会十分低效.因此，我们采取快速傅里叶变换进行优化.TOC o 1-5 h z HYPERLINK l bookmark58 o Current Docume

15、nt 设p二a-10n+a10n-i+fa10i+a，其中0a9,aeN,0in,ieNnn-110ii(5-1)q二b10m+b10m-i+b10i+b，其中0b9,beN,0im,ieNmm-110ii(5-2)令多项式A(x)二axnfaxn-1ffax1fa，(5-3)nn-110B(x)二bxmfbxm-1ffbx1fb.(5-4)mm-110(5-5)C(x)二A(x)B(x).注意到p二A(10),q二B(10).因此pq二C(10)二A(10)B(10).(5-6)将大整数相乘转化为多项式的乘法,应用快速傅里叶变换,即可得出结果.六、参考文献1、大学数学学习指南线性代数(第二版),山东大学出版社,刘建亚,吴臻,秦静,史敬涛,许闻天,张天德,金辉,胡发胜,宿洁,崔玉泉,蒋晓芸编著2、大学数学线性代数(第二版),高等教育出版社,上海交通大学数学系线性代数课程组编著3、Int