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

1、精选优质文档-倾情为你奉上利用快速傅里叶变换(FFT)计算多项式乘法作者:宋振华摘要本文将讨论快速傅里叶变换(FFT),利用FFT设计一种算法,使多项式相乘的时间复杂度降低为,以便在计算机上高效计算多项式乘法.关键词:快速傅里叶变换、多项式乘法目录1、 引言2、 算法概述三、引理1、多项式的表示(1)系数表达形式(2)点值表达形式(3)插值2、利用离散傅里叶变换(DFT)与FFT导出结果的点值表达形式(1)单位复数根(2)离散傅里叶变换(DFT)(3)通过快速傅里叶变换(FFT)计算向量3、 利用FFT计算逆DFT,将结果的点值表达形式化为系数表达形式(1)在单位复数根处插值(2)利用FFT计

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

3、.3、 引理1、 多项式的表示(1)系数表达对于次数为的多项式,其系数表达是一个由系数组成的向量.考虑用系数形式表示、次数为的多项式、的乘法运算.记.有.可以看出,采取逐个计算的方式进行求解,其时间复杂度为.(2)点值表达a.定义:一个次数为的多项式的点值表达就是由一个有个点值对组成的集合,使得对于,所有的各不相同.b.点值表达下多项式乘法对于次多项式,设其点值表达式分别为:,:设,由于的次数为,因此必须对和的点值表达式进行扩展,使每个多项式都包含个点值对.给定,的扩展点值表达:,:.则的点值表达形式为:.因此,计算点值表达式的时间复杂度为.(3)插值 求值运算的逆(从一个多项式的点值表达形式

4、确定其系数表达形式)称为插值.下面将证明,个点求值运算与插值运算是定义完备的互逆运算.a. 多项式的点值表达可以唯一确定多项式的系数表达形式.多项式的点值表达等价于矩阵方程:=.(3-1-3-a)记系数矩阵为,由Vandermonde行列式可知,.而,有,因此,即可逆.因此对于给定点值表达,我们能够唯一确定系数表达式,且.b.对于次数为的多项式函数,插值算法基于如下Lagrange公式:.(3-1-3-b)容易验证,Lagrange公式的计算复杂度为.因此,个点求值运算与插值运算是定义完备的互逆运算,它们将多项式的系数表达与点值表达进行相互转化.2、 利用离散傅里叶变换(DFT)与FFT导出结

5、果的点值表达形式(1)单位复数根次单位复数根是满足的复数.次单位复数根恰好有个:对于,这些根是.由Euler公式可知,这个单位复数根均匀地分布在以复平面原点为圆心的单位圆圆周上.称为主次单位根,所有其他次单位根都是的幂次.个次单位复数根,.,在乘法意义下构成一个群,该群与群同构.由此,可以得到如下推论:a. ,有.(3-2-1-a)b. ,.(3-2-1-b)c. 若,=.(3-2-1-c)对推论c的证明:由a可知,.所以对于,有.得证.d.且不能被整除,有.(3-2-1-d)对推论d的证明:.(2)离散傅里叶变换(DFT)对于次多项式,其系数形式为.(3-2-2-1)设,(3-2-2-2)则

6、向量(3-2-2-3)就是系数向量的离散傅里叶变换.(3)通过快速傅里叶变换(FFT)计算向量.对于次多项式,不妨假设.对于不为的整数次幂的情况类似,此处不再讨论.FFT采取了分治策略,采用中偶数下标与奇数下标的系数,分别定义两个新的次多项式:,(3-2-3-1).(3-2-3-2)注意到包含所有偶数下标的系数,包含中所有奇数下标的系数,于是有:.(3-2-3-3)所以,求在,.,处的值的问题转化为:a.求次数为的多项式,在点,.,处的取值.b.根据(2-2-3-3)综合结果.根据(2-2-1-c),式(2-2-3-3)不是由个不同值组成,而是仅由个次单位复数根所组成,每个根正好出现次.因此,

7、我们递归地对次数为的多项式,在个次单位复数根处进行求值.这些子问题与原始问题形式相同,但规模变为一半.下面确定DFT过程的时间复杂度.注意到除了递归调用外,每次调用需要枚举中所有元素,将划分为、,分别与多项式,相对应.其时间复杂度为.因此,对运行时间有下列递推式:.(3-2-3-4)求解该递推式,有.(3-2-3-5)采取快速傅里叶变换,我们可以在时间内,求出次数为的多项式在次单位复数根处的值.3、 利用FFT计算逆DFT将结果的点值表达形式化为系数表达形式(1)在单位复数根处插值根据(2-1-3-a),我们可以把DFT写成矩阵乘积,其中是一个由适当幂次填充成的Vandermonde矩阵.=(

8、3-3-1-1)易知.即可逆.下面证明处元素.(3-3-1-2)考虑处元素:.(3-3-1-3)当时,;当时,根据(2-2-1-d)可知,.满足.(3-3-1-4)给定逆矩阵,可以求出.其中.(3-3-1-5)(2)利用FFT计算逆DFT比较(3-3-1-5)和(3-2-2-2)可知,对FFT算法进行如下修改,即可计算出逆DFT:把与互换,用替换,并且将计算结果每个元素除以.因此,我们也可以在时间内计算出逆DFT.四、算法具体流程1、加倍多项式次数通过加入个系数为的高阶项,把多项式和变为次数为的多项式,并构造其系数表达.2、求值通过应用阶的FFT计算出和长度为的点值表达.这些点值表达中包含了两

9、个多项式在次单位根处的取值.3、逐点相乘把的值与的值逐点相乘,可以计算出的点值表达,这个表示中包含了在每个次单位根处的值.4、插值通过对个点值应用FFT,计算其逆DFT,就可以构造出多项式的系数表达.由于1、3的时间复杂度为,2、4的时间复杂度为,因此整个算法的时间复杂度为.五、算法的实际应用:计算大整数乘法在密码学等领域中,经常需要进行大整数乘法运算.如果对整数逐位相乘然后相加,其时间复杂度为.当规模巨大时,这种算法将会十分低效.因此,我们采取快速傅里叶变换进行优化.设,其中(5-1) ,其中(5-2)令多项式,(5-3) .(5-4) .(5-5)注意到,.因此.(5-6)将大整数相乘转化为多项式的乘法,应用快速傅里叶变换,即可得出结果.6、 参考文献1、 大学数学学习指南线性代数(第二版),山东大学出版社,刘建亚,吴臻,秦静,史敬涛,许闻天,张天德,金辉,胡发胜,宿洁,崔玉泉,蒋晓芸编著2、 大学数学线性代数(第二版),高等教育出版社,上海交通大学数学系线性代数课程组编著3、 Introduction to Algorithms(Third Edition),Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein4、