傅立叶,两个1元多项式相乘快速算法

【】计算两个一元多项式相乘的系数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大大减少运算量，以数值计算的角度来考虑，是很有作用小学数学教学论文的。
文献：
VictorY.Pan.StructuredMatricesandPolynomials.UnifiedSuperfastAlgorithms[M].NewYork：Springer，2001.等