二维 DFT 和 DCT 的 Systolic 阵列

超级计算中一个活跃的研究领域是将某些有限和,如离散富里叶变换(DFT)、离散余弦变换(DCT),映射到多处理机阵列上。本文首先通过二维DFT的行列分解算法流程图,给出了计算二维DFT的二种Systolic阵列:一种是由N_1个处理器组成的线性阵列,所花时间步为O(N_1N_2)(设二维DFT为N_1×N_2长的),与行列分解算法在单处理机上顺序执行所花时间相比,加速比为O(N)(设N_1=N_2=N)。这一结果无论是在时间消耗,还是在PE数量上都是目前最优的。另一种是由N_1×N_2个处理器组成的矩形阵列,所需时间为O(N_1+N_2),与行列算法在单处理机上顺序运行所花时间相比,加速比为O(N~2)(这里仍假定N_1=N_2=N)。本文还给出了二维DCT的与二维DFT相似的Systoilc阵列结构。不难将上述阵列推广到多维的情况。     

大型稀疏线性代数迭代库在YH 机上的高效实现

本文讨论了大型稀疏线性代数方程组的迭代算法、加速方法、存贮技术及并行算法。结合向量机特点,采取有效程序优化措施,开发研制了标量和向量库程序。在ＹＨ系列机上试算结果表明：大型稀疏线性代数向量迭代库比标量迭代库速度有较大提高。当Ｎ≥１００时,在ＹＨ─１机上加速比约２～８;在ＹＨ─２机上约２～７;当迭代次数增加时,加速比提高更明显;库中共轭梯度（ＣＧ）加速方法能有效地加快收敛,可减少迭代次数一半以上。     

多元多项式乘积的 FPT算法

本文详细讨论了多元多项式乘积的多项式变换(FPT)算法。首先给出了二元的情况,然后推广到了一般多元多项式,最后给出了这种算法在计算二维循环卷积中的应用,由此可见,这种算法在计算多维卷积和多维DFT 时是很有效的。