一种求解线性稠密方程组的并行超松弛迭代算法.docVIP

  A parallel SOR iterative algorithm for solving dense linear systems of equations# ZHANG Yun, CUI Shubiao, ZHOU Huamin* 5 10 15 20 25 (State Key Laboratory of Materials Processing and Die Mould Technology, Huazhong University of Science Technology) Abstract: The Successive Over-Relaxation method (SOR) is a stationary iterative solver for linear systems of equations which is widely used. However, it is difficult to be parallelized due to tight data correlations in each iteration step. A parallel SOR algorithm for dense linear systems of equations is considered in this paper, the convergence property of which is identical to the original SOR method. The iteration steps of the original SOR are first replaced by an equivalent iterative form and thus data correlations in each iteration step are decreased. And then a matrix partitioning method and a prejudication algorithm are employed to perform computing pipelines in iteration steps. Since there are time lags between computing pipelines on different processors, indispensable synchronizations can be replaced by asynchronous communications and thus the communication cost for parallel computing would be greatly decreased. Numerical experiments have been performed on both a quad-core personal computer and a 6-nodes computer cluster. The numerical results show that the present parallel SOR method can yield a parallel speed-up factor of 3.5 on the quad-core personal computer and acquire a practical linear parallel speed-up on the 6-nodes computer cluster. Key words: SOR; parallel computing; system of linear equations; iterative methods; pipelines; matrix partition 0 Introduction The Successive Over-Relaxation (SOR) method is one of earliest point iterative methods for solving large linear systems of equations. It is still quite popular in a few application areas, and it can be quite successful when combined with more efficient methods as a preconditioning technology. For the numerical solution of a large nonsingular l