




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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、
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 蜂疗技术治疗
- 杰家传媒行业分析
- 护士半年年终总结
- 胸腔积液超声诊断
- 2025年泰州市九年级中考语文一模试题卷附答案解析
- 2025年安全生产标准化建设安全培训试题汇编
- 制作-步骤流程总结
- 2025年摄影师职业技能鉴定试卷:摄影作品市场价值评估与推广技巧提升策略试题
- 探索建筑设计中空间约束考量
- 公共服务机构市民表扬奖励
- 中职高考数学一轮复习讲练测专题一 集合与充要条件(测)原卷版
- 《抽水蓄能电站系统建模与特性分析》6300字(论文)
- 最终版附件1:“跨学科主题学习”教学设计(2025年版)
- 财务管理委托代理会计服务 投标文件(技术方案)
- 北京三甲中医疼痛科合作方案
- QCT957-2023洗扫车技术规范
- 2023超星尔雅《创新创业》答案
- 施工放样测量记录表
- GB 6944-2012 危险货物分类和品名编号(高清版)
- 600MW发电机组自动装置整定计算及仿真
- IT行业薪酬管理制度示例某软件公司薪酬体系设计方案
评论
0/150
提交评论