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

CN431258/ T P
 ISSN 1007130X
    计算机工程与科学
COMPUTER ENGINEERING & SCIENCE
2010 年第32 卷第10 期
 Vol 32, No 10, 2010
文章编号: 1007130X( 2010) 10008005
一种求解线性方程组的SOR 并行算法
*
A Class of Parallel SOR Met hod for
Solving Linear Equat ion Syst ems
张 云, 周华民, 崔树标, 李德群
ZHANG Yun, ZHOU Huamin, CUI Shubiao, LI Dequn
( 华中科技大学材料成形与模具技术国家重点实验室, 湖北 武汉 430074)
( State Key Laboratory of Material Processing and Mold and Die Technology, Huazhong University of
Science and Technology, Wuhan 430074, China)
摘 要: 逐次松弛迭代算法( SOR) 是求解线性方程组的一种常用迭代算法, 当系数矩阵正定时, 它具有较快的收敛速
度。但是, 由于每个迭代步内存在数据相关, 它难以实现并行计算。目前的SOR 并行算法采用数据分解的方法, 但由于该
法并行区域过小, 同步通讯代价大, 并行效率低。本文提出了SOR 的一种新型并行算法, 该算法与传统 SOR 方法等价, 具
有相同的收敛性和迭代结果。该并行算法通过矩阵分块增大了可并行计算的区域, 并引入流水线技术, 利用各处理器间通
讯与计算时间的重叠, 获得较理想的并行加速效率。通过多核微机以及小规模集群上的数值实验证明, 本文提出的SOR
并行算法在求解大型稠密线性方程组时具有较好的并行效率。
Abstract: The Successive OverRelaxation ( SOR) method is a class of solvers for the linear equation systems in use. It
converges quickly if the coeff icient mat rix is posit ively def inite. Since there ar e data corr elations in each iteration step, it is
thought to be unsuitable for parallel computing. T he general parallel algorithms for SOR, which use a data decomposit ion
met hod, is inefficient due to t he tiny parallel regions and the resulting expensive time cost for synchronizations. A class of
par allel SOR met hod is pr oposed in this paper . The par allel SOR method present ed is equivalent to the original SOR method
and has an ident ical conver gence ratio and identical solutions as the original. In t his method, the sizes of parallel regions are
incr eased using a partit ioning method, and then pipeline is brought in to over lap communicat ions and computing, thus a per
fect parallel efficiency can be achieved. Numer ical experiments ar e perfor med on both multicore per sonal computers and a
small scale computer cluster , the par allel SOR method pr oposed is pr oved efficient for lar gescale dense linear equation sys
tems.
关键词: 松弛迭代; 并行计算; 线性方程组; 流水线
Key words: SOR; par allel computing; linear system of equations; pipeline
doi: 10. 3969/ j. issn. 1007130X. 2010. 10. 021
中图分类号: T P301; O242. 26 文献标识码: A
1  引言
大型稠密线性方程组由于求解计算量大, 在现有计算
机硬件条件下求解时间长, 并行计算是缩短其求解时间的
常用途径之一。一般而言, LU 分解、高斯消元法等直接解
法具有内在的并行性, 易于实现并行计算。SOR 等迭代方
法与直接解法相比, 能够将求解线性方程组的计算量从 O
( n
3
) 减少到O( n
2
) , 在数值计算领域应用广泛。为求解 n
阶非奇异线性方程组:
80
* 收稿日期: 20090110; 修订日期: 20090409
基金项目: 国家自然科学基金资助项目( 50675080) ; 教育部高等学校博士点基金资助项目( 20060487056)
作者简介: 张云( 1981 ) , 男, 湖南澧县人, 博士生, 研究方向为计算机数值模拟与并行计算; 周华民, 教授, 博士生导师, 研究方向为
材料成形过程模拟、注塑模CAD、CAE、智能化注塑机; 崔树标, 讲师, 研究方向为塑料成形CAD/ CAE/ CAM 、数值模拟、虚拟现实、
人工智能; 李德群, 教授, 博士生导师, 研究方向为机械成形加工工程及自动化。
通讯地址: 430074 湖北省武汉市珞瑜路 1037 号华中科技大学材料成形与模具技术国家重点实验室; Tel: ( 027) 87543492,
13659829536; Email: marbl ezy @ 163. com
Address: Stat e Key Laborat ory of Mat erial Processing and Mold and Die T echnology, Huaz hong Universit y of Science and T echnolo
gy, 1037 Luoyu Rd, Wuhan, Hubei 430074, P. R. China