2.4.2 基于多项式直接代入的改进算法

更新于 2026年11月21日 版权声明
2.4.2 基于多项式直接代入的改进算法

例如,当N=16,记旋转因子图示为wp,FFT的多项式运算结果的前8 项如表2-1 所示。将表2-1 按行数序号的奇偶分成两个表,其中序号为偶数的列表如表2-2 所示。

表2-2 N=16时FFT的多项式运算结果的偶数项

图示

序号为奇数项时实数与旋转因子的乘法次数:

θ(α0)+θ(α1)+θ(α2)+θ(α3)+θ(α4)+θ(α5)+θ(α6)+θ(α7)=0+1+2×2+4×4=21

而序号为偶数时,可以合并相邻同类项,根据表2-2 基向量减少了一半,此时实数与旋转因子乘法次数减少:

θ(α0)+θ(α1)+θ(α2)+θ(α3)=0+1+3+3=7

据此有FFT多项式串行算法如下。

算法2.2 FFT多项式串行算法

图示(https://www.daowen.com)

表2-3 FFT算法与多项式算法规模比较

图示

由表2-3 可见,当N不大于32 时,多项式算法性能优越;当N=16 时,多项式算法乘法次数相比FFT乘法次数只有43.75%;当N=32 时,多项式算法乘法次数相比FFT算法乘法次数只有75%;当N≥64 时,多项式算法时间复杂度要大于FFT,根据定理2.1有:

图示

多项式算法的根本优点在于:一是便于大粒度并行计算。在实践中,多核片上系统(MPSoC)一般是强实时专用系统,处理器实时中断处理外部事务频率高,处理器不可能被算法完全占用。Cooley-Tukey并行算法前后两层级之间存在迭代关系,只有在前一级的蝶形计算全部完成的基础上,才能进行下一层次的运算,为了实现同步,处理器需要进行轮询同步,容易造成同步等待而消耗时间。而采取多项式算法,实现并行完全不需要考虑同步,每层都可以独立完成计算,大大减少了并行的消耗。二是便于稀疏数据处理。在多项式算法中,执行操作图示,可以预先判定X2c+X2c+1或者X2c-X2c+1的值是否为零,如果为零,可以避免乘法操作,从而有效减少了稀疏数据处理的计算量。

算法2.3 多项式FFT并行算法

图示

续表

图示

根据Cooley-Tukey并行算法,输入规模为N的计算,每一层计算将有NP进程需要同步,每个进程同步等待次数的期望值为图示。如果每次等待消耗时间为t,每层的迭代计算需要同步等待图示。按照多项式并行算法,则同样有信号量互斥同步。设有N个进程互斥访问N个共享存储变量,设置同步信号量有N个来进行同步控制,那么每个进程互斥等待的概率为图示。如果N=32,NP=4,则P=0.09085。由此,处理器同步开销得到了有效降低。

✍AI写作