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

利用快速傅里叶变换计算多项式乘法第1页，课件共41页，创作于2023年2月问题引入：整数乘法1.n位数与1位数相乘78125×8000526逐位相乘乘法计算次数=n位数的位数时间复杂度第2页，课件共41页，创作于2023年2月问题引入：整数乘法2.n位数与n位数相乘78125×16384312500625000234375468750128000000078125(2)中每一位同(1)逐位相乘(1)(2)乘法计算次数n项2n位(最多)加法计算次数总计算次数时间复杂度第3页，课件共41页，创作于2023年2月问题引入：整数乘法两个n位数相乘的时间复杂度为当n非常大时(如n>10000时)，利用计算机直接计算两个n位数的乘积将十分低效。为了高效进行大整数乘法，需要一种更高效的算法。利用快速傅里叶变换计算n位大整数乘法，其时间复杂度为第4页，课件共41页，创作于2023年2月一、多项式的两种表达形式1、系数表达多项式：其系数为：将系数写为向量形式：系数向量称为多项式的系数表达形式。第5页，课件共41页，创作于2023年2月两个n次多项式的加法(1)(2)＋(3)其中，，,...,第6页，课件共41页，创作于2023年2月系数表达下两个n次多项式的加法的系数向量的系数向量的系数向量n+1次加法运算时间复杂度：第7页，课件共41页，创作于2023年2月系数表达式下两个n次多项式的乘法的系数向量的系数向量令将与中的系数两两相乘。其时间复杂度为计算C(x)系数第8页，课件共41页，创作于2023年2月2、点值表达对于n次多项式任取n+1个不同的点第9页，课件共41页，创作于2023年2月根据n+1个点唯一确定n次多项式系数:未知量:已知量n+1元一次方程组第10页，课件共41页，创作于2023年2月矩阵形式的方程组=系数矩阵行列式不为0证明方程具有唯一解只需证明第11页，课件共41页，创作于2023年2月证明系数矩阵行列式不为0=由于当时，必有，所以≠矩阵满秩因此，方程组具有唯一解。Vandermonde行列式第12页，课件共41页，创作于2023年2月点值表达任取n+1个不同的点，可确定唯一n次多项式。换句话说，对于：可以作为n次多项式的一种表述形式。点值表达：第13页，课件共41页，创作于2023年2月点值表达下n次多项式,的加法：：的点值表达为：：注意A(x),B(x)在相同的n+1个位置取值点值表达为：时间复杂度为第14页，课件共41页，创作于2023年2月需要将A(x),B(x)点值表达扩展到2n+1对：：点值表达下n次多项式的乘法点值表达为：可以得到C(x)中n+1对点值：而C(x)是2n次多项式表示C(x)第15页，课件共41页，创作于2023年2月：：点值表达下n次多项式的乘法扩展点值表达为：可以得到C(x)点值表达：时间复杂度为2n+1次乘法运算第16页，课件共41页，创作于2023年2月系数表达与点值表达是等价的系数表达：点值表达：求值插值拉格朗日插值公式定义完备，互逆运算第17页，课件共41页，创作于2023年2月系数表达与点值表达比较及转换系数表达点值表达求值插值普通乘法时间点值乘法时间时间时间假设存在第18页，课件共41页，创作于2023年2月一种快速计算多项式乘法的算法(系数表示)1、对A,B进行求值，时间复杂度算法描述：在上述假设下，求值与插值时间复杂度均为2、对A,B进行点值乘法，时间复杂度3、对结果进行插值，时间复杂度A,B为多项式的系数表达形式假设确实成立,借助FFT能够实现第19页，课件共41页，创作于2023年2月二、快速求值求值时间若任取2n+1个点直接求值，计算所需时间:计算加法所需时间:在每一个点处求值时间对所有点求值时间:需要降为:第20页，课件共41页，创作于2023年2月二、快速求值求值时间适当选取2n+1个点与算法，每个点求值时间可以降为:对所有点求值时间将为:特殊取值：2n+1次单位复数根第21页，课件共41页，创作于2023年2月单位复数根定义：n次单位复数根是满足的复数.n次单位复数根恰好有n个求解由欧拉公式知,第22页，课件共41页，创作于2023年2月单位复数根主n次单位根：n次单位复数根几何意义k=1左图为8次单位根在复平面上的分布。n次单位根在复平面上均匀分布其他n次单位根都是的幂次0(8)1345726第23页，课件共41页，创作于2023年2月单位复数根的性质n个n次单位复数根乘法意义下构成群：在乘法意义下构成群。该群与群(整数模n)同构，即第24页，课件共41页，创作于2023年2月单位复数根的性质消去引理：对于偶数n>0：第25页，课件共41页，创作于2023年2月单位复数根的性质折半引理：n为偶数n个n次单位复数根的平方的集合，就是n/2个n/2次单位复数根的集合。第26页，课件共41页，创作于2023年2月单位复数根的性质折半引理的几何意义：8次单位复数根在复平面上的分布0(8)1234567第27页，课件共41页，创作于2023年2月单位复数根的性质折半引理的证明：由消去引理知：此时又有第28页，课件共41页，创作于2023年2月单位复数根的性质求和引理：k是非负整数，k不是n的倍数求和引理证明：====0k不是n的倍数，第29页，课件共41页，创作于2023年2月离散傅里叶变换(DFT)回顾我们希望计算在处的值（即在n+1个n+1次单位根处）假设A以系数形式给出，系数向量第30页，课件共41页，创作于2023年2月离散傅里叶变换(DFT)定义结果：就是系数向量的离散傅里叶变换采用普通乘法进行计算，时间复杂度为第31页，课件共41页，创作于2023年2月离散傅里叶变换与快速傅里叶变换(FFT)有必要利用单位复数根的特殊性质，降低时间复杂度引入快速傅里叶变换计算离散傅里叶变换第32页，课件共41页，创作于2023年2月离散傅里叶变换与快速傅里叶变换(FFT)对于n次多项式：此处假设n+1是2的整数次幂偶数下标奇数下标第33页，课件共41页，创作于2023年2月离散傅里叶变换与快速傅里叶变换(FFT)对于求A(x)在,,...,处取值转化为：求(n-1)/2次多项式,在,,处取值处取值即,,...,折半引理然后将结果相加得到A(x)第34页，课件共41页，创作于2023年2月离散傅里叶变换与快速傅里叶变换(FFT)递归地处理分解成两个相似的子问题，规模减半拆分时,需要把n+1个系数拆成两部分.时间复杂度FFT第35页，课件共41页，创作于2023年2月离散傅里叶变换与快速傅里叶变换(FFT)时间复杂度递推公式规模为n的时间复杂度拆分成2个n/2规模的子问题拆分问题代价求解该递推式，有采用FFT,可以在时间内实现插值第36页，课件共41页，创作于2023年2月插值时间利用快速傅里叶变换实现插值回顾不妨先考虑n次多项式A(x)的插值依然假设n+1是2的整数次幂第37页，课件共41页，创作于2023年2月利用快速傅里叶变换实现插值离散傅里叶变换中的一项：将离散傅里叶变换写成矩阵形式：=易知：可逆未知量第38页，课件共41页，创作于2023年2月利用快速傅里叶变换实现插值下面证明：处元素考虑：处元素当时：当