论文部分内容阅读
【摘要】直接计算两个一元多项式相乘的系数需要O（n2）的运算量。本文介绍了一种超快的算法——用快速傅立叶变换实现两个一元多项式相乘的快速算法。该算法是通过快速傅立叶变换、快速傅立叶变换逆变换以及卷积来实现的，其运算量为O（nlog2n）。
【关键词】快速傅立叶变换（FFT）；快速傅立叶变换的逆变换（IFFT）；卷积；运算量
近十几年来，很多从事数值计算的工作者在探讨快速算法这个比较热门的课题，并且也取得了一定的成果。在本篇论文中，我们用快速傅立叶变换这个工具来研究两个一元多项式相乘的快速算法。
一、用快速傅立叶变换实现两个一元多项式相乘的快速算法
1.离散傅立叶变换及其逆变换的定义
首先我们来介绍一下离散傅立叶变换多项式形式的定义。
记：，P(x)为一个n-1次多项式，wn为1的开n次方根
则离散傅立叶变换（DFT）的定义为（多项式形式）：
我们同样也可以得到离散傅立叶逆变换的定义为（多项式形式）：
接下来我们来介绍离散卷积的定义。设和是以N为周期的周期点列，即x(k)和h(k)满足：，……则x(k)和h(k)的离散卷积定义为：，
2.用快速傅立叶变换实现两个一元多项式相乘的快速算法
我们首先来介绍离散卷积的计算，直接利用公式做数值计算总共需要N（N-1）个加法和N2个乘法。我们可以把式分解为如下三步来做。
①计算x(k)和h（k）的离散傅立叶变换：
②计算积：Y(n)=X(n)H(n)
③计算逆傅立叶变换：
接下来我们来介绍快速傅立叶变换实现两个一元多项式相乘的快速算法。
记：，分别为m、n次的两个一元多项式
设为m+n次的多项式
记，则
我们可以把式分解如下三步来计算：
①计算，，这步计算过程也就是把两个多项式做离散傅立叶变换的过程。
②计算：，
③计算和输出：，，
这步计算过程其实就是把多项式做离散傅立叶逆变换的过程，也就是我们得到的用快速傅立叶变换实现两个一元多项式相乘的快速算法。通过以上三步，我们可以看出，用快速傅立叶变换实现两个一元多项式相乘的快速算法，其实也就是卷积的计算方法。
下面我们给出一道例题：
例：，，计算
解：设，∵
接下来我们求出即P(x)的傅立叶逆变换：
∴P(x)的系数∴.
二、用快速傅立叶变换实现两个一元多项式相乘的快速算法的运算量分析
对于两个一元多项式相乘，如果用传统的算法，算出所有Pj（0≤j≤m+n），所需的乘法次数为(n+1)(m+1)。又需要nm次加法，相当于每个x的乘幂项的系数中加法次数都比乘法次数少一次，而乘幂项的个数为2m+1。于是，若用传统算法，两个m次多项式相乘所需要的算术运算次数为(m+1)2+m2，即运算量为O(nm)；而通过上面给出的算法即用快速傅立叶变换实现两个一元多项式相乘的快速算法的运算量则为O((m+n+1)log2(m+n+1))，通过比较，我们可以看出用FFT可以大大减少运算量，从数值计算的角度来考虑，是很有意义的。
参考文献：
[1]VictorY.Pan.StructuredMatricesandPolynomials.UnifiedSuperfastAlgorithms[M].NewYork：Springer，2001.等
【关键词】快速傅立叶变换（FFT）；快速傅立叶变换的逆变换（IFFT）；卷积；运算量
近十几年来，很多从事数值计算的工作者在探讨快速算法这个比较热门的课题，并且也取得了一定的成果。在本篇论文中，我们用快速傅立叶变换这个工具来研究两个一元多项式相乘的快速算法。
一、用快速傅立叶变换实现两个一元多项式相乘的快速算法
1.离散傅立叶变换及其逆变换的定义
首先我们来介绍一下离散傅立叶变换多项式形式的定义。
记：，P(x)为一个n-1次多项式，wn为1的开n次方根
则离散傅立叶变换（DFT）的定义为（多项式形式）：
我们同样也可以得到离散傅立叶逆变换的定义为（多项式形式）：
接下来我们来介绍离散卷积的定义。设和是以N为周期的周期点列，即x(k)和h(k)满足：，……则x(k)和h(k)的离散卷积定义为：，
2.用快速傅立叶变换实现两个一元多项式相乘的快速算法
我们首先来介绍离散卷积的计算，直接利用公式做数值计算总共需要N（N-1）个加法和N2个乘法。我们可以把式分解为如下三步来做。
①计算x(k)和h（k）的离散傅立叶变换：
②计算积：Y(n)=X(n)H(n)
③计算逆傅立叶变换：
接下来我们来介绍快速傅立叶变换实现两个一元多项式相乘的快速算法。
记：，分别为m、n次的两个一元多项式
设为m+n次的多项式
记，则
我们可以把式分解如下三步来计算：
①计算，，这步计算过程也就是把两个多项式做离散傅立叶变换的过程。
②计算：，
③计算和输出：，，
这步计算过程其实就是把多项式做离散傅立叶逆变换的过程，也就是我们得到的用快速傅立叶变换实现两个一元多项式相乘的快速算法。通过以上三步，我们可以看出，用快速傅立叶变换实现两个一元多项式相乘的快速算法，其实也就是卷积的计算方法。
下面我们给出一道例题：
例：，，计算
解：设，∵
接下来我们求出即P(x)的傅立叶逆变换：
∴P(x)的系数∴.
二、用快速傅立叶变换实现两个一元多项式相乘的快速算法的运算量分析
对于两个一元多项式相乘，如果用传统的算法，算出所有Pj（0≤j≤m+n），所需的乘法次数为(n+1)(m+1)。又需要nm次加法，相当于每个x的乘幂项的系数中加法次数都比乘法次数少一次，而乘幂项的个数为2m+1。于是，若用传统算法，两个m次多项式相乘所需要的算术运算次数为(m+1)2+m2，即运算量为O(nm)；而通过上面给出的算法即用快速傅立叶变换实现两个一元多项式相乘的快速算法的运算量则为O((m+n+1)log2(m+n+1))，通过比较，我们可以看出用FFT可以大大减少运算量，从数值计算的角度来考虑，是很有意义的。
参考文献：
[1]VictorY.Pan.StructuredMatricesandPolynomials.UnifiedSuperfastAlgorithms[M].NewYork：Springer，2001.等