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

A PARALLEL SOLVER FOR CERTAIN CYCLIC TRIDIAGONAL TOEPLITZ SYSTEMS ON DISTRIBUTED MEMORY MULTICOMPUTERS

提出一类 Toeplitz循环三对角方程组的一种分布式并行算法 .在求解由一阶线性双曲型方程 (如迁移方程 )在一定边界条件下导出的隐式差分方程组时 ,要重复地求解此类 Toeplitz循环三对角方程组 .算法基于对系数矩阵的分解 ,贯彻并行算法设计中“分而治之”的原则 ,充分利用了系数矩阵结构的特殊性 .算法实现中通过秦九韶公式的运用 ,避免了不必要的冗余计算 ;理论分析和数值试验表明 ,算法是数值稳定的 ,且当方程组规模充分大时 ,该算法加速比趋近线性加速比的理想情况 .

A parallel algorithm for certain cyclic tridiagonal Toeplitz systems on distributed memory multicomputers is presented. This kind of cyclic tridiagonal Toeplitz systems occurs repeatedly in the solution of implicit finite difference equations derived from linear first order hyperbolic equations, i.e. the transport equation, under a variety of boundary conditions. The algorithm is based on the factorization of the coefficient matrix and the principle of “divide and conquer” in designing parallel algorithms. Full use is made of the special structure of the coefficient matrix. There is less redundancy computation caused by parallelization. The communication mechanism is simple. The algorithm is stable and its parallel efficiency is high. The analysis of complexity and numerical experiments shows that the algorithm's speedup satisfy S p(n)→p(n→+∞) . This is the best result a parallel algorithm can reach. The results of numerical experiments about the algorithm on a distributed memory multicomputer are also given.