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

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.