一类Toeplitz三对角方程组的一种分布式并行算法

文中提出一类Toeplitz三对角方程组的一种分布式并行算法。该算法以系数矩阵的分解为基础，充分利用了系数矩阵结构的特殊性，算法因并行化而引入的冗余计算量非常少，算法的通信机制简单，通信量仅与处理 机台数p有关，与方程组规模n无关，算法具有很高的并行效率，理论分析和数值试验表明，其加速比Sp(n)→p(n→ ∞），此为线性加速比的理想情况。文中给出了算法在分布存储多计算机系统上的数值试验结果。

A Parallel Solver for Certain Toeplitz Tridiagonal Systems on Distributed-Memory Multicomputers

The tridiagonal Toeplitz linear systems occur repeatedly in the solution of the implicit finite difference equations derived from linear first order hyperbolic equations, i.e. the Transport equation, under a variety of boundary conditions. Interest in fast direct methods for solving these kind of linear systems has long been a hot spot of research. A parallel algorithm for certain tridiagonal Toeplitz linear systems on distributed-memory multicomputers is presented. Derivation of the algorithm is introduced. The algorithm is based on the factorization of the coefficient matrix and the principle of ‘divide-and-conquer’ in designing parallel algorithms. Authors make full use of the special structure of the coefficient matrix. By using the customary nesting procedure, Horner's formula, authors avoid the necessary of quantities αi, (－α)i(i=2,3,…,m) and (αm)i, (－αm)i(i=2,3,…,p-1). This reduces the algorithm's redundancy computation caused by parallelization. The complexity of the algorithm is analyzed using LogP model. Its communication mechanism is very simple. The communication complexity is only related to p, the number of processors, and not related to n, the size of the matrix. The algorithm's parallel efficiency is high. The analysis of complexity and numerical experiments show that the algorithm's speedup satisfy: Sp(n)→p(n→+∞). This is the best a parallel algorithm can reach. The algorithm has been implemented on parallel computers. The results of numerical experiments about the algorithm on a distributed-memory multicomputer are presented in this paper.