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

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

利用近似三对角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.