近似三对角Toeplitz方程组的快速分布式并行算法  

A Parallel Algorithm for Near Tridiagonal Toeplitz Equations on Distributed-Memory Multicomputers

作　　者：单润红[1] 高峰[2] 宋君强[1] 李晓梅[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073 [2]西安电子科技大学天线与微波技术国家重点实验室,西安710071

出　　处：《计算机研究与发展》2004年第7期1281-1285,共5页Journal of Computer Research and Development

基　　金：国家自然科学基金项目 ( 4 0 2 45 0 2 3 )

摘　　要：利用近似三对角Toeplitz矩阵的特殊结构 ,提出了一种新的求解近似三对角Toeplitz方程组的快速算法 在三对角Toeplitz矩阵的近似LU分解的基础上 ,利用“分而治之”的思想 ,并结合秦九韶技术和特殊的数学技巧减少大量的冗余计算 ,提出了求解近似Toeplitz三对角方程组的快速分布式并行算法 ,并在理论上证明了算法具有近似于线性的加速比 最后通过数值实验证明 ,新的并行算法具有较高的并行效率 ,并且当矩阵阶数n足够大时 。Making use of the special structure of near tridiagonal Toeplitz matrix,a new fast algorithm is presented to solve near tridiagonal Toeplitz equations. Based on the near LU factorization of tridiagonal Toeplitz matrix and by making use of the principle of 'divide and rule',a fast distributed parallel algorithm is put forward for near tridiagonal Toeplitz equations. By introducing 'Qing-Jiushao algorithm' and special mathematic skill,the new parallel algorithm avoids redundant operations. Also proved in theory is that the algorithm's speedup is closed to linearity. Finally,numerical experiments show that the new parallel algorithm have a high parallel efficiency. And above all,if n is large enough,the speedup is approximate to linearity.

关 键 词：TOEPLITZ 三对角方程组 并行算法 加速比 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]