关键词: 松弛迭代, 并行计算, 线性方程组, 流水线

Abstract:

The Successive OverRelaxation (SOR) method is a class of solvers for the linear equation systems in use. It converges quickly if the coefficient matrix is positively definite. Since there are data correlations in each iteration step,it is thought to be unsuitable for parallel computing. The general parallel algorithms for SOR,which use a data decomposition method,is inefficient due to the tiny parallel regions and the resulting expensive time cost for synchronizations. A class of parallel SOR method is proposed in this paper. The parallel SOR method presented is equivalent to the original SOR method and has an identical convergence ratio and identical solutions as the original. In this method,the sizes of parallel regions are increased using a partitioning method,and then pipeline is brought in to overlap communications and computing,thus a perfect parallel efficiency can be achieved. Numerical experiments are  performed on both multicore personal computers and a smallscale computer cluster,the parallel SOR method proposed is proved efficient for largescale dense linear equation systems.

Key words: SOR;parallel computing;linear system of equations;pipeline