三对角线性方程组的一种有效并行算法

AN EFFECTIVE PARALLEL ALGORITHM FOR TRIDIAGONAL LINEAR EQUATIONS

本文提出一种求解严格对角占优的三对角线性方程组的并行算法（简称ＰＰＤ算法），新算法计算复杂性约为８ｎ，与最优串行算法追赶法的计算复杂性相同，通信复杂性为常数．目前求解此类方程组的最优并行算法的计算复杂性约为１７ｎ，通信复杂性约为ｌｏｇＰ，相对而言ＰＰＤ算法的计算性能和通信性能都有大幅度提高．试算结果表明，加速比呈线性增加，并行效率达到９０％以上．

This paper gives a parallel algorithm,PPD algorithm, for the solution of diagonally dominant tridiagonal linear systems. Its computation complexity is about as same as the best sequential algorithm and its communication complexity is a constant. But now the computation and communication complexity of the best parallel algorithm are about 17 n and log P . It implements PPD algorithm on a MPP supercomputer. The results show that speedup improves linearly and the efficiency of our method is up to 90%.