二维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阵列结构。不难将上述阵列推广到多维的情况。

VLSI计算模型上二维DFT的Wavefront阵列

给出了基于VLSI计算模型的二维DFT(离散富里叶变换 )的阵列算法及其处理流程图 ,在此基础上 ,利用矩阵乘的Wavefront阵列 ,提出了二维DFT的Wavefront阵列计算结构 ,并与其Systolic阵列进行了比较 ,得出了二维DFT的Wavefront阵列优于其Systolic阵列的结论 .

复矩阵乘的快速算法

介绍了文献 [1]中一类复矩阵乘的快速算法 ,提出并证明了这类矩阵的 2个重要性质及相关的结论 ,同时给出了另一类复矩阵的矩阵乘快速算法 ,其算法复杂性与 [1]相同 .

多元多项式乘积的FPT算法

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

基于无浮点小波视频压缩算法

将视频压缩和小波理论的最新发展———整数小波和二进制小波相结合,提出只需整数加法和移位的视频压缩算法,该算法所需的硬件成本比一般的基于三维小波变换的算法成本大大降低,而速度大幅度加快.

三维DFT的FPT算法

本文导出了一种三维离散富氏变换(DFT)的快速多项式变换(FPT)算法,并对该算法的计算量与通常所用算法(行列法)进行了比较,最后对算法的优劣作了总结.

三维数字循环卷积的二元多项式变换算法

讨论了用二元多项式变换计算三维数字循环卷积的方法,给出了运算量的估算.此法与常用的FFT方法、WFTA方法、一元FPT方法比较,所需运算量有所减少.更为重要的是从理论上完善了多元多项式变换计算高维数字循环卷积的方法.

有理域上的二元多项式变换

引进二元多项式变换的概念 ,旨在利用其CCP特性计算多维数字循环卷积 ,仿照一元多项式变换的研究方法 ,详细研究了二元多项式变换成立的条件 .当模M1(z1) ,M2 (z2 )是可约多项式时 ,建立了有理域上二元多项式变换成立的 5个充要条件和 3个充分条件 ,并证明了这种变换具有循环卷积特性 (CCP) .

一种适合于求实系数多项式近似复根的迭代法

提出了一种适合于求实系数多项式近似复根的迭代法,并进行了收敛性分析,给出了若干数值实例.该方法与切线牛顿法共同构架了复数域上求非线性代数方程近似解的基本方法.在切线牛顿法失效时它可替代使用.其收敛的阶为3,高于切线牛顿法的收敛阶2.特别地,与已有的抛物迭代法相比较,该方法是单步而非多步.

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

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

多元多项式乘积的多项式变换算法

详细讨论了多元多项式乘积的多项式变换(FPT)算法.首先给出了二元的情况,然后推广到了一般多元多项式乘积的情况,这为计算多维卷积和多维DFT提供了新的途径.

三维DFT的TPF算法

本文详细导出了一种三维离散富氏变换的快速多项式变换算法,并对该算法的计算量与通常所用算法(行列法)进行了比较,最后对界法的优劣作了总结。

计算一类数字变换的收缩阵列

本文以DFT的收缩(Systolic)阵列结构为基础,给出了一类数字变换在这种结构上的VLSI并行实现,这些变换包括离散富里叶变换,离散余弦变换,离散正弦变换,离散Hartley变换,数论变换和多项式变换。这些基本的阵列结构是构造大规模收缩阵列的基础。