一种求解线性方程组的SOR并行算法  

A Class of Parallel SOR Method for Solving Linear Equation Systems

作　　者：张云[1] 周华民[1] 崔树标[1] 李德群[1] 

机构地区：[1]华中科技大学材料成形与模具技术国家重点实验室,湖北武汉430074

出　　处：《计算机工程与科学》2010年第10期80-84,共5页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(50675080);教育部高等学校博士点基金资助项目(20060487056)

摘　　要：逐次松弛迭代算法(SOR)是求解线性方程组的一种常用迭代算法,当系数矩阵正定时,它具有较快的收敛速度。但是,由于每个迭代步内存在数据相关,它难以实现并行计算。目前的SOR并行算法采用数据分解的方法,但由于该法并行区域过小,同步通讯代价大,并行效率低。本文提出了SOR的一种新型并行算法,该算法与传统SOR方法等价,具有相同的收敛性和迭代结果。该并行算法通过矩阵分块增大了可并行计算的区域,并引入流水线技术,利用各处理器间通讯与计算时间的重叠,获得较理想的并行加速效率。通过多核微机以及小规模集群上的数值实验证明,本文提出的SOR并行算法在求解大型稠密线性方程组时具有较好的并行效率。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.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]