（计算数学专业论文）大型带状线性方程组的并行算法.pdf

砖七工业大学硕七论文摘要 摘要 许多大型科学与工程计算问题最后常需要求解一个或一些系数矩阵为大型 稀疏矩阵的线性方程组。本文研究了系数矩阵为带状矩阵的线性方程组a x = 厂 的并行算法。主要讨论了如下几个问题： ( 1 ) 对带状线性方程组的系数矩阵爿作适当的行分配，在行作用方法的基础 上给出了行作用方法的并行实现方法。在理论上，算法只要系数矩阵4 是非奇异 矩阵就能够收敛，而且有较好的并行性，在h pr x 2 6 0 0 集群上进行数值试验，验 证了算法的计算结果与理论相一致。 ( 2 ) 研究了一种适合于m i m d 分布式存储并行机的交替方向法，理论上证明 了在系数矩阵为h e r m i t e 正定矩阵和m 矩阵时算法的收敛性，讨论了参数f 的收 敛范围，最后在h pr x 2 6 0 0 集群上进行数值试验，结果表明此算法有良好的收敛 性与并行性。 关键词并行算法，行作用方法，正定矩阵，m 矩阵，h pr x 2 6 0 0 集群 西北二t ：业大学硕十论文a b s t r a c t a b s t r a c t l i n e a re q u a t i o n sw i t hl a r g es p a r s ec o e f f i c i e n tm a t r i c e sa r i s ei nm a n y p r a c t i c a ls c i e n t i f i ca n de n g i n e e r i n gp r o b l e m s t h ew o r kp r e s e n t e di nt h i s p a p e rf o c u s e so np a r a ll e li t e r a t i v ea l g o r i t h m sf o rs o l v i n gs u c hl a r g e 1 i n e a rs y s t e m s h e r e ，i ti st ob ed i s c u s s e da sf o l l o w s ： ( 1 ) w i t hs u i t a b l ed e c o m p o s i t i o no fb a n d e dc o e f f i c i e n tm a t r i x 。a p a r a l l e li t e r a t i r ea l g o r i t h mo nd i s t r i b u t e d m e m o r ym u l t i c o m p u t e ri s e s t a b l i s h e di nc h a p t e rt w o ，w h i c hi sb a s e dr o wa c t i o nm e t h o d a c c o r d i n gt o t h e o r e t i c a la n a l y s i s ，i ti sc o n v e r g e n ta n dh a sg o o dc o n v e r g e n c ei ft h e c o e f f i c i e n tm a t r i xi san o n s i n g u l a rm a t r i x m o r e o v e r ，e x a m p l e sh a v eb e e n i m p l e m e n t e do nh pr x 2 6 0 0c l u s t e r ，a n dt h ed a t av e r i f yt h a tt h en u m e r i c a l r e s u l t so ft h i sa l g o r i t h mc o i n c i d ew i t hi t st h e o r e t i c s ( 2 ) ap a r a l l e ls p l i ti t e r a t i o na l g o r i t h mf o rm i m dd i s t r j b u t i v i t y m e m o r yc l u s t e ro ns o l v i n g1 i n e a rc o e f f i c i e n tm a t r i c e si se s t a h l i s h e di n c h a p t e rt h r e e c o n v e r g e n c ei sp r o v e dw h e nt h ec o e f f i c i e n tm a t r i xi s h e r m i t ep o s i t i v ed e f i n i t e m a t r i xo rm m a t r i x d i s c u s s i n gc o n v e r g e n c e r a n g eo fp a r a m e t e rr i nt h ee n d ，e x a m p l e sh a v e b e e ni m p l e m e ：t e do n h p r ) ( 2 6 0 0c l u s t e r ，a n dt h ed a t av e r i f yt h a tt h ea l g o r i t h mh a sf a v o r a b l e a s t r i n g e n c ya n dp a r a l l e l i s m k e y w o r d s ：p a r a l l e la l g o r i t h m ， r o w m a t r i x ，m m a t r i x ，h pr x 2 6 0 0 a c t i o n m e t h o d ，p o s i t i v ed e f i n i t e c l u s t e r 西北工业大学硕士学位论文第一章预备知识 1 1引言 第一章预备知识 众所周知，在科学与工程计算中，许多问题最后常归结为求解一个或一些大 型稀疏矩阵的线性方程组，由于在理论和实际应用上的重要性，线性方程组的并 行求解是数值算法研究中最重要的课题之一，其研究十分活跃。现今科学研究与 大型工程项目中各种复杂的计算课题对计算机的要求越来越高，串行计算机已不 能满足这一需求，而且串行算法不能直接用于并行计算机，所以面向并行计算环 境研究大型稀疏线性方程组的高效并行算法显得尤为重要。 虽然线性代数方程组的求解方法和数值计算软件包均很成熟，但随着并行计 算机的发展及现今科学研究与大型工程项目中各种复杂的计算课题对计算速度 的更高要求，使得数值计算方法和相应的数学软件包都产生了变化，从而相应的 线性方程组的有效并行计算的求解也引起了人们的普遍关注。并行算法设计需要 考虑计算机体系结构与编程模式的影响，一方面要可进行并行计算，另一方面要 有较小的存储要求，最终获得计算的高性能。对于所要计算的数学问题。如果传 统数值方法已经具备良好的和明显的并行性，则可以直接采用并行算法设计，不 要从数值分析的角度进行并行化的工作；相反，倘若传统方法并没有良好的并行 性，则应对其进行并行性改造和创新。并行算法要求各处理机的运算具有运算无 关性，即并行性要好，要尽量减少通讯量和同步开销。然而解线性代数方程组的 并行算法，基本上都是原有的串行算法，现有的方法几乎不是收敛性不好，就是 并行性不好，因此大量的研究工作在于开发传统算法的并行性，使之适应并行计 算机计算：如g a u s s 消去法、共轭梯度法、j a c o b i 方法等；另一方面则致力于 研制新的有效的并行解法：如三对角方程组的分裂法、循环约亿法、多分裂并行 迭代法、异步迭代并行算法等”j 。1 9 8 5 年，o l e a r y 和w h i t e 1 6 提出了并行多 分裂方法并进行了深入研究，它被认为是一类重要的并行数值方法。近年来引起 了数值计算工作者的极大兴趣，进一步改进了其算法模型，完善了收敛理论。异 西北工业大学硕十学饥论z第一章预备知识 步迭代并行算法【2 j 也是随多处理机的出现而发展起来的一类新的算法。而并行迭 代解法已取代直接法成为求解大型线性方程组的最重要的一类方法。针对系数矩 阵为大型稀疏矩阵的线性方程组的并行迭代解法有：并行j a c o b i 型方法、红黑 或多色排序实现s o r 并行处理、a d i 方法、多分裂方法等，【1 】中给出了一种直 接法求解块三对角线性方程组的并行算法；【4 】给出了一种并行迭代解法，但要 达到各处理机负载平衡要求条件较高。 本篇论文中所要讨论的就是系数矩阵为带状矩阵的线性方程组a x = f ， ( a r ，x ，f r ”) 的并行迭代解法。首先针对系数矩阵为带状矩阵的线性方 程组给出了行作用方法的并行实现，理论上只要系数矩阵是非奇异的，此算法永 远是收敛的，而且具有好的并行效果。在h pr x 2 6 0 0 集群上进行数值试验，结果 证明了此算法的可行性。在多分裂迭代算法的基础上，给出了带状线形方程组的 交替方向迭代算法，并证明了系数矩阵为h e r m i t e 难定矩阵和m 矩阵时算法的 收敛性，在h pr x 2 6 0 0 集群上进行数值试验，结果表明算法有良好的并行性。 1 2 基本概念及理论准备 1 2 1 行号 p 处理机台数 t 时间( 单位：秒) l 迭代次数 s 相对燃比( 蔫鬻篇淼 e 相对并行效率( 鲁) i 绷橄瓮甏黹戮黼lp 台处理机用此算法所用的时间j 人 误差( l a x 一毗) 西北1 ：业人学硕十学位论文 第一章预备知识 1 2 2 相关结论 定义1 1 设爿为打阶矩阵，若对任意n 维非零向量x r 4 ，都有 r a x 0 成立，则称4 为f 定矩阵 定义1 2 设a 为门阶h e r m i t e 矩阵，若对任意，z 维非零向量z c ”，都有 j “a x 0 成立，则称4 为h e r m i t e 半f 定( 非负定) 矩阵：又若对任意门维非零向量x c ”， 都有 一i x 0 成立，则称爿为h e r m i t e 正定矩阵 定义1 3 【7 】p - 正则分裂：设矩阵4 是n 阶方阵，若矩阵膨和满足： a = m 且m “+ n 为h e r m i t e j 下定矩阵，则称爿= m n 为a 的p 正则分 裂 定义1 4 【5 】 a = ( a o ) ，占= ( 气) 均为删九实矩阵，如果 日 0 时，即满足a 。 o ( i = 1 , 2 ，m ，j = 1 , 2 ，”) ， 称a 为正矩阵 定义1 5 【5 】 若一个拧阶实矩阵爿的逆矩阵爿 - 0 ，则称爿为单调矩阵 定义1 6 如果矩阵a = ( a 。) 。，的主对角线以外的元素非正，且爿。为非负 矩阵，即 0 ( ，j ) ，a “0 则称a 为m 矩阵 西北工业人学硕士学能论文第一章预备知识 定义1 7 2 】设爿为力阶方阵，我们称分裂爿：m n 为 ( 1 ) 正规分裂，如果m 。1 0 且n 0 ( 2 ) 非负分裂( 弱萨规分裂) ，如果m “0 ，m “n 0 且m f | 1 0 ( 3 ) 第一类弱非负分裂，如果m “0 且 f 。n 0 ( 4 ) 第二荚弱非负分裂，如果m 1 0 且忖- 。口 引理1 i 若a 为实对称矩阵，则a = m 一是p 正则分裂的充要条件 是。小1 引理1 2 【4 】设4 r ，a ：m n 为矩阵4 的弱正规分裂( 第一类弱非 负分裂) 或正规分裂，贝j j p ( m 一1 1 当且仅当月一1 口 引理i 3 1 5 1 没4 是m 矩阵，当爿的任意元素( 一个或多个) 增大，但保持 主对角线外的元素仍然为非证值时，则所得的矩阵曰也是m 矩阵，且有 曰一1 a 引理i 4 1 5 1 设4 是m ，矩阵，则它的胛个顺序主子矩阵都是m ，矩阵 1 3 本文的主要工作 本文主要研究了带状线性方程组的一些并行算法，主要内容包括以下几个方 面： 1 第二章中给出的行作用方法的一种并行实现方法，只要系数矩阵a 是非 奇异的，而且不考虑舍入误差的影响，这种迭代方法永远是收敛的，理论上得到 了保证。最后在l 弹r x 2 6 0 0 集群上进 亍了数值计算，并与多分裂算法作了比较， 结果表明此算法的可行性。 2 在第三章中研究了一种适合于m 1 m d 分布式存储并行机的交替方向迭代 算法，形式为 ( ，十r 缈) ( ，+ f 矿) ( x “”一x ) = 一口r ( a x 一，) 4 两i l g ：业人学硕+ 学位c 文 第一章预备知识 其中a = w + v ，x r “，a ，w ，v ，j r ，k = o ，1 ，理论上证明了在 系数矩阵为h e r m i t e 正定矩阵和m 一矩阵时算法的收敛性，并对系数矩阵4 的两 种不同的分裂方式进行了比较，讨论了实参数r 的收敛范围，最后在h pr x 2 6 0 0 集群上进行了数值试验，结果表明此算法有良好的收敛性与并行性。 5 西北1 ：业大学硕十学位论文 第一章带状线性方程组行怍用方法的并行实现 第二章带状线性方程组行作用方法的并行实现 在科学与工程阀题中经常遇到的许多微分方程，经过适当的差分或有限元离 散而形成为系数矩阵为带状矩阵的线性方程组 a x = ， ( 2 1 ) 式中：a r “”，f r ”。设t ：y 半- 带宽分别为尼。，t ，对于任意的f ，= l ，2 ，订 有，当一k u ，一f k 。时，a 。0 ：当j f k 时，a 口= 0 并假 设矩阵4 为满足条件氏+ k ，。 ”的带状矩阵。本文中的矩阵均为前面所定义的 带状矩阵。 本章给出了行作用方法的一种并行实现方法。由 2 7 可知，只要系数矩阵4 是非奇异的，而且不考虑舍入误差的影响，这种迭代方法永远是收敛的。并且在 h pr x 2 6 0 0 集群上进行了数值计算，且与多分裂算法作了比较，结果表明此算法 的有效性与良好的并行性。 2 1 行作用方法原理 设带状线性方程组a x = f ( a r ”，f r ”) 可表示为 d 。圳，十i d 。+ i ，女 口ip i a ，t in 0 一“ d n n z ： i 驯 ( 2 2 ) 首先以二阶线性方程组为例，求解二阶线性方程组的解，在几何上是求出 在_ o 屯平面上两条直线，和如交点的坐标。从而o x ：平面任意一点x ( 0 ) 出发，向 作垂线相交于x ( ”，继而从x ( 1 ) 出发，向1 2 作垂线相交于x ( ”，继续这个过程就 6 而屯：稚“ viiiioiooooooooo火 “ 一 盘 孔 “ 盯 虬 口 q ； 西北工业大学硕士学位论文 第章带状线性方程组行作用方法的并芤实现 得到一个序列 x ，序列中的任何一点x 都可以看作二阶线性方程组的一个 近似解。可以看出，哪一条直线看作是“第一条”将导致不同的序列 x 。 ，也 就是说，方程的排列次序将影响迭代过程。将方程组( 2 2 ) 的系数矩阵a 的转置矩 阵4 7 按列划分为a 1 = f a i , 口2 ，口”1 ，口表示4 的第f 个列向量。不失一般性， 可假定f ，口 = 1 ，方程组的第f 个方程一具体可写为 口。卫l = z( 扛l 州2 一，以) 可以推得格式 工9 = 上o 。+ ( ，一 口，x o - 1 ) 口 雄立行作用方法扶代格式如下： ) ：x 扯( 任瓤r ”) x n j “1 = x 扯+ ( ，一 口7 ，x 咔 ) 口( 1 ，挖) 工“1 = 工1 ( 女= o ，1 2 。) 三维投影技术，划分集合 1 ，2 ，门 为一些三元素组： n ( m o d 3 ) = 0 ( 1 ，2 ，3 ) ，( 4 ，5 ，6 ) ，- 一，( 月一2 ，胛一1 ，? ) n ( m o d 3 ) = 1 ( 1 ，2 ，3 ) ，( 4 ，5 ，6 ) ，- 一，( ”一3 ，玎一2 ，n - 1 ) ，( n - 2 ，n - 1 ，h ) n ( m o d 3 ) = 2 ( 1 ，2 ，3 ) ，( 4 ，5 ，6 ) ，- 4 ，n - 3 ，n - z ) ，( ”一2 ，玎一1 ，门) 对于三元素( “- 1 ，“2 ，i 十3 ) 对应的三个方程 可以推得 ： a i , x = z + ： 万m ：x = ，+ ， f x ( 。= x ( “) + q 口+ 屈口+ 2 + 只口+ 3 l 磁( ，屈，一) 7 = 丘 7 多北一e 业大学硕士学位论文 第二章带状线性方程组行作用方法的并行实现 其中 m ”1 ，矿i 庇= | l a i + 2 , a j + l ”，1 f + 2 p 2 ，扩2 a i + 3 矿2 厶= f , , 1 - p o 如_ 一】 七”，一) 推广为p 维投影技术，不论p 个方程的排列次序，理论上只要系数矩阵是可逆的， 则对于任意x ( 。) 迭代过程永远收敛，为了有好的并行性，本章采用p 个方程的法 向量之间两两相互正交。 2 2 并行算法迭代格式 不妨假设处理机台数为p ，记第i 台处理机为c ( k l ，2 ，p ) ，设 n = p m ( 优2 ，m z ) ，且将爿，f ，x 进行分块如下； a = a l a 2 ； 4 口一i a p ，f = i l t lp x l x 2 ： x d l 工p 其中4 ，葺分别为a ，f ，x 的( i - 1 ) m + l ，i m 行 将矩阵a ，t ( f - l ，2 ，p ) 按列划分为 a t = ( q 1 ，口j 2 ，心“) 对于p 元素( f ，i + m ，f + ( p 1 ) 肌) 对应的p 个方程： 口= ， 。： 口：，工 = j + 。( f = 1 ，m ) 一如叫。：h x = “州。 1 j 1 j 1 j 3 3 3 + + + 口 口 口 2 3 件 件 件 口 仃 口 rl rl rl 堕韭些大学艰士学位论文第一二章带状线性方程组行作用方法的并行实现 只要p 满足：p 去 就有口。口，口；之间总能两两是相互正交的 记置= 一n 一+ 。n n 一+ ) + 。，若已经求出，确定) 墨，使满足 ( x “一x 斗) - ls 由于口：上s ，口：上s ，口：- k s ，所以 s p a 珂似，口，口： 上s x “一x = 口。口f + 口：口：十+ 口，口： 并由x ( ) 乃，x ( ) 一+ 。，工+ ) 一+ ( p l m ，可得 其中 m ：= h 疗门 a 2 一, a i k 口f 阱窿幻 心口幻 k i 口：i m 巨 = l h i 口幻i 心口幻 陆口妇 l = z k 叫 z 犷k 叫 “巾。一k 叫 因为 口二，口： = 0 ( 后，j , k = l ，2 ，p ) ，所以m 可简化为 m = 口f ，iq i 融2 , a 2 。 k 口幻 ( 2 3 ) ( 2 。4 ) ( 2 5 ) 出上述推导过程知 彰，彰 ( ，= l ，2 ，p ) 在0 台处理机单独计算，处理过程完 全是并行的。于是可由( 2 3 ) 式唯一求得( f _ 1 , 2 ，p ) 。由以上推导得到迭代 9 旦! 塑：些查竺婴! ! ! 堡鲨奎 蔓兰童堂鉴垡丝查矍塑堑堡旦查鲨盟茎堑塞墨 格式 够( q ，呸，) 1 = 厶 一= ( 任耐。r “) + = 妒+ q 日卜够卜+ n ： ( 2 6 ) 工( 制= x 川+ q 口? + 呸+ + a p a ： ( j = l ，2 ，坍) 其中m ，厶为( 2 4 ) 与( 2 5 ) 式所示矩阵 2 3 并行实现过程 将矩阵爿由左至右按带状顺序划分为4 i ，a 2 ，a h ，4 + + k ， 目日4 ：= ( o ，o ，。，甜。+ l ：，- 日。一。) 7 ，a ：= ( o ，o , a k - i , i o k ，：，口。，。一 + 。) 7 ， 一a 气= ( a t l ，q 2 2 , a n n ) 7 ， 。= ( ，q l + u ，0 一，o ) 7 2 3 1 存储方法 在第i 台处理机p 中分别存入，爿r ”2 ，( ，= 1 , 2 ，l + 吒+ 七坩) ， ( k = 1 , 2 ，蜥) z ，葺( i = 1 , 2 ，p ) 以这样的存储方式节省了很大的存储 空间，仅是编程过程较为复杂。 2 3 2 循环计算过程 ( 1 ) 第i ( i = l ，p ) 台处理机p 进行一次并行通讯，将只台处理机中 一m ，传到f 。台处理机中，在只中计算得到“”： f o rj 2 1t om 一丘。 铲( z 厂州) 口? ， l “i ) = 0 一口? e n n 西北工业大学硕士学位论文第二章带状线性方秽组行作用方法的并行实现 ( 2 ) 第i ( i = 1 ，p ) 台处理机e 进行一次并行通讯，将p + 。台处理机中 x l ，坼。传到只台处理机中( 当，= 聊一o + e 。) ) ，在只中计算得到毫“1 ： f o rj = m k 、。t o m q = ( ，厂 口? ，纠) 咖门 x p “= j j 一d 。口? e n d 即在每一台处理机尸中，逐行循环运算一次。 ( 3 ) 第f ( f - l ，p ) 台处理机只中判断0 “”一1 | | e ( f 为容差) 是否都 成立，若对所有处理机都满足此不等式，则停机：否则，返回( 1 ) 继续循环， 直到满足所有不等式成立为止。 可以看出，本算法在计算过程中循环次只需要相邻处理机间的通信，总通 信次数为2 ，并且以带状顺序方式存储数据，使得存储量要求 t d , ，且具有较好 的并行性，适合在m i m d 分稚式存储环境下进行并行计算。 若厅不能被p 整除，则处理机按顺序存储，肖i n - n p p 台处理机存放 f 露p 】+ 1 个行，另外一些处理机按顺序分别存放【p 】个行，同时对于| 以及 右端项z 中存入对应的处理机中，依次按顺序存放，要尽量使每台处理机的负载 大体均衡。以减少等待时间。 本章算法由 2 7 知，只要系数矩阵是可逆的，则迭代算法永远收敛。 2 。4 数值算例 例1 对于形如( 2 2 ) 式中的系数矩阵a ，可以表示为： 西北： 业人学硕十学何论文 第一二章带状线性方程组行作爿j 方法的并行实现 其中 一1 4一l 一1 一l4 4 置 c 爿：垦 g 一，爿。蛾一 c ma m b j = c i = 一i 。n ( 2 7 ) 取初始向量为 。= ( o0 o ) 1 ，在= 5 0 ，m = 1 0 0 0 ，终止条件为s = 1 1 0 圳时，在 h pr x 2 6 0 0 集群上进行并行测试( 计算时间以秒为单位) ，计算结果见下表1 。 4 = 薹j ；! | j i ；圣； ，哆= e = 一3 一z 一4 ，= ，在_ 。j = ； ， m = 8 0 0 0 0 及终止条件为s = 1 1 0 一。时，在h pr x 2 6 0 0 集群上进行并行测试( 计 例3 椭圆型偏微分方程 e 窘+ q 孑+ ( c i 蒯c 2 ) 塞+ ( d , s i n 2 x y + d 2 叫o u + 觑= 。 0 x y 1 和边界条件 甜ub k = ：o 。：= 弹u 。1 ：= ，, ：= 1 1 。0 + + c 口c o 跚s x x y ( 其中，e ，q ，c i ，c 2 ，d l ，d 2 和e 是常数) 分别取e = e = e = 1 ，c t = c 2 ：d i = b = 0 ，步长为1 1 0 1 ，采用五点差分 格式得到的线性代数方程组，在终止条件为占= 1 1 0 。o 时，在h pr x 2 6 0 0 集群上 l，_。【 | ， 项 崭 i 右 4 0 ，。，- i l 4 西北工业大学硕j 学位论文 第二章带状线性方程- 舞i - 7 作用方法的并行实玖 进行并行测试( 计算时间以秒为单位) ，试验数据结果见下表3 。 例4 对于形如( 2 7 ) 式的矩阵爿，其中 4 = 三j ：! ：j 。，e = e = 一凡。，右端项，= 取初始向量为 0 。= ( o0 o ) ，在n = 3 ，脚= 8 0 0 0 0 ，终止条件为占：l x l o m 时，在 h p r x 2 6 0 0 集群上进行并行测试( 计算时间以秒为单位) ，试验数据结果见下表4 。 表l 表3 给出了本章算法与多分裂方法的数据结果。表4 给出了本章算法 的数据结果，对于多分裂方法失效。 表1 例1 的计算结_ 累( n = 5 0 m = 1 0 0 0 ) 处理机台数l2 468 时间( 秒)3 4 4 9 3 82 6 1 0 7 9 2 5 7 1 4 72 2 8 6 6 8 1 8 0 6 8 7 加速比1 3 2 1 2 13 4 1 41 5 0 8 5 效率 迭代次数 0 舭一州。 3 2 4 8 0 6 6 0 6 3 2 4 8 0 3 3 5 4 3 2 4 8 o 2 5 1 5 3 2 9 2 1 9 0 9 1 0 2 3 8 6 3 2 4 8 3 3 1 5 9 e 一0 9 3 3 1 5 9 e - 0 93 3 1 5 9 e 0 95 5 2 2 8 e 0 9 3 3 1 5 9 e 0 9 多分裂算法 一_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ - - _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ - _ _ _ _ _ _ _ _ _ - _ _ _ _ _ 一 处理机台数 1 24 时间( 秒) 2 2 7 8 8 加速比 5 4 0 5 1 3 1 4 9 7 7 7 4 2 2 6 0 5 6 68 6 3 5 2 95 1 1 5 9 3 1 8 8 63 9 5 9 6 效率o 6 5 7 5 0 , 6 5 1 40 5 3 1 4 o 4 9 4 9 迭代次数 1 7 7 4 8 02 5 7 4 9 34 9 8 、lll， 西般l ：业人学硕士学何论文第二章带状线性方程组行作用肓法的并行实现 表2 例2 的计算结果( n = 3 ，m = 8 0 0 0 0 ) 表3 例3 的计算结聚( n = 1 0 0 ，州= 1 0 0 ) 8 舭一州。 1 1 7 6 3 e 0 91 1 7 6 3 e 0 9 1 1 7 6 3 e - 0 91 2 0 5 9 e - 0 91 1 7 6 3 e - 0 9 多分裂算法 l 北r ：业大学硕十学位论文第二章带状线性方程组行作用方法的并行实现 算例分析： 1 本章算法根据矩阵的特点，以带状顺序存储，在存储数据上节省了很大 的空间。 2 从数据表可以看出，本章算法是可行的，得到方程组的近似解的精度也 很高并且与理论分析结果相一致。在m i m d 分布式存储环境下求解是完全可以 实现的。实际计算表明，针对例4 多分裂方法失效，而行作用方法只要系数矩阵 a 可逆而且不考虑舍入误差的影响，迭代方法是永远收敛的，适用范围比较广， 特别适用于病态方程组，而多分裂方法要求系数矩阵满足的条件比较强。 3 本文的并行算法简单易行，便于上机实现。 西北。i ：业大学硕十学位论文第二章带状线性方程组的交替方向法 第三章带状线性方程组的交替方向法 本章研究了形式为 ( ，+ f ) ( ，+ r v ) ( x + 1 1 一x 。) = 一a r ( a x 一，) 的适合于m i m d 分布式存储并行机的交替方向迭代算法，其中a = w + v ， x 彤，a ，w ，v ，j r ，( k = o ，1 ，) ，a = 2 ，r 为实参数。理论上证明了 在系数矩阵为h e r m i t e f 定矩阵和m 一矩阵时算法的收敛性，并对带状线性方程 组a x = ，就文中提出的两种分裂方式进行了比较，讨论了参数f 的收敛范围， 最后在h pr x 2 6 0 0 集群上进行了数值试验，结果表明此算法有良好的收敛性与并 行性。 3 1 并行算法迭代格式 大型线性方程组的求解是大规模科学与工程计算的核心，随着计算机的飞 速发展，需要求解的问题的规模越来越大，迭代法己取代宣接法成为求解大型 线性方程组的最重要的类方法。目前各种新的迭代法不断涌现 3 3 】，本章也给 出两种不同分裂方式的交替方向迭代算法。 设带状线性方程组a x = ，可以表示为： 4召。 c 24 2 曰2 g 。 马。 爿2 。 工一 屯 ： x 2 h 一 叠。 其中a ，、c 。、b ，为f f 矩阵x ，z 为t 维列向量 z ： 以， 。 ( 3 1 ) 假设处理机台数为p ，记第i 台处理机为只( f ：1 ，2 ，p ) ，设 r l = m p ( m 2 ，m z ) ，则对( 3 1 ) 式的系数矩阵a 作如下分裂 西北工业火学硕士学位论文 第二章带状线性方程组的交替方向法 爿= + v( 3 2 ) 则由 ( j + r w ) ( i + r v ) ( x “一x 1 ) = 一a r ( a x “一f ) 其中矩阵，+ r w ，i + r v 均是可逆的，口= 2 ，得到算法迭代格式 x “一x = 一2 r ( 1 + r v ) 一( j + r w ) 一1 ( a x 一，) = 辛x 。+ 1 = x 一( j r + r v ) 一1 ( ，+ r w ) 一 2 r ( a x 一，) 】 工扯+ 1 1 = f 1 2 r ( i + r v ) 一1 ( j + r ) 一1 a ) x + 2 r ( 1 + r v ) 一1 ( j + f ) 一1 f ( 3 3 ) 得算法迭代矩阵为占。= ( 1 - 2 f ( ，+ r y ) 一1 ( ，+ r 矿) 一1 a ) 从式( 3 3 ) 可以看出，关键的问题是求解以，+ r w ，i + r v 为系数矩阵的 线性方程组，那么适当的分裂系数矩阵a 显得尤为重要。这里给出了如下两种 分裂方式，使算法更具并行性。 第一种分裂方式，取 w = 爿。马 口 c 3a 3b 2 口 v = c 2 。4 。也。 口 口 c 2爿2曰2 口 g4 反 第二种分裂方式，取 1 7 口 c 2 。4 。 西北：f 业大学硕十学位论文 第三章带状线性方程组的交替方向法 v = 一1 爿b 三4 ， c 3 1 1 _ a 3 b 3 昙a 。 ! 爿， c 2 = 1a 2 四2 1 二一， 3 2 并行实现过程 c 2 = 1 a 2 剃垦，l 昙如 c 4 1 ，a 4 b 4 z 1 j = 月2 h i c 2 。昙气 将矩阵爿由左至右按带状顺序划分为a - ，a 2 ，a h + l ，a i + l + i 。 即4 = ( o ，o ，掣，扎) 7 ，爿：= ( o ，o ，吨一，口。母。) 7 ， ，爿。+ 屯= ( 码：，) 7 ，氐= ( 吼。码j + ，o ，o ) 1 3 2 1 存储方法 在第i 台处理机只中分别存入爿”，( ，= 1 ，2 ，l + 丸+ 钆) ， 西北工业大学硕士学位论文 第三章带状线性方程组的交瞀方向法 ( k = 1 ，2 ；- - , 掰) ，葺( i = l ，2 ，p ) 。以这样的存储方式节省了很大的存 储空间，仅是编程过程较为复杂。 3 2 2 循环计算过程 对于第一种分裂方式： ( 1 ) 第i ( f _ l ，p ) 台处理机p 进行一次并行通讯，得到。在只中计算： y i = 一c t r ( 1 + r 形) 。( _ ，x i “一，：) 其中彬，4 ，z ，t 分别为w ，a ，f ，x 的第f ( i = 1 ，2 ，p ) 块。即在每台处理机中， 进行一次l u 分解求解方程组，并行运算一次。 ( 2 ) 第i ( f = l ，p ) 台处理机只进行一次并行通讯，在只计算： l “1 ) = 0 。) + ( ，+ r 杉) 。以 其中为v 的第f ( f _ 1 ，2 ，p ) 块。即在每台处理机中，进行次三u 分解求解 方程组，并行运算一次。 ( 3 ) 第，( f = l ，p ) 台处理机只中判断k + 1 ) - - 。8 o 得p ( m “+ ) o ，m “+ r 是h e r m i t e 正定 矩阵，由引理1 2 知算法迭代格式收敛 证毕f i 定理3 2 设a 是h e r m i t e e 定矩阵，则对任意的f 0 ，第二种分裂方式迭 代格式收敛 证明 由已知，a 是h e r m i t e e 定矩阵，则由 ( ，+ r ) ( ，+ r y ) ( x 。一x ) = 一2 r ( a x n 一，) 其中矩阵j + r w ，i + r v 均是可逆的，得到迭代矩阵 吃= ( ，一2 f ( j + f 矿) 一1 ( ，+ f r v ) 一a ) 于是 吃= ( j r 一2 r ( ，+ r y ) 。( ，+ f r v ) 。a ) = ( ，一2 r ( ，+ f y ) 。( ，+ f ) 一( r v + v ) ) = ( “。f y ) 。( ，+ r w ) 。( ( j r r v ) ( - r v ) ) 则矩阵a = m n 是h e r m i t e 正定矩阵，其中 m = ( i + r w ) ( 1 + r v ) ，= ( i 一丁) ( ，一f 矿) 因为对于第二种分裂有v “= w ，所以 f h + r = ( ，+ r v ) h ( j r + r w ) h + ( ，一r w ) ( t r v ) = i + r a h + f 2 v h w h + j r a + 2 w v 2 ! 型坚e 兰坠堂堡堂竺堡塞 笙三兰壹鉴丝些塑堡塑堕窭篁查塑兰 = 2 ，+ 2 f 2 w v 显然2 ，+ 2 r 2 矿是h e r m i t ef 定矩阵由引理i 2 知算法迭代格式收敛 证毕| | 定理3 3 锄是m 啦啭耔娓蜊n ( 刳c 渊2 驯， 为矩阵4 的主对角线元素，则对任意初始向量x ( “，第一种分裂方式迭代格 式收敛 证明 由( ，+ r w ) ( + r v ) ( x “一x ) = 一2 r ( a x ( “一，) ，其中矩阵 j + f 缈，+ f y 均是可逆的，得到迭代矩阵 或= ( i - 2 f ( ，+ r 矿) 。( ，+ f ) 一a ) 则对于分裂a = m n ，其中 m = ( ，+ r ) ( ，+ r v ) ，= ( ，一r ) ( ，一r v ) 有m = ( j + f y ) 一1 ( ，+ f ) ，n = f ，一r w ) ( t r v ) 因为 ，+ r y = 所以( ，+ f y ) = 叫，+ 磁) 。曩 i t c 2 ni + r a 2 ， ， 叫“呜，) 1 g ( “呜， 吼 r a +， 哦，暇 a+， ，e 丑； g 码，日嘲 弋 ， 啦pq ， ，吐 n 叫 西北工业大学硕十学位论文第三章带状线性方程组的交替方向法 由引理1 3 知( ，+ r a ，) ( 江l ，2 ，2 n ) 是m 一矩阵，所以 ( ，+ f 4 ) 0 ，一r ( ，+ f 4 ) 。c 0 ，一f ( ，+ f 4 ) - 1 e 口 推得( ，+ r y ) - 1 0 同理( j + f ) 。0 ，于是m 一1 口 由已知，。 - 0 由已知，嘛列n 旧) ( f ：t 小伽，醐一兆c h 啦口， 因此0 所以分裂a = m n 为正规分裂，由引理1 2 知迭代格式对任意初 始向量x ( o ) 均收敛 3 4 数值算例 例1 对于形如( 2 7 ) 式的系数矩阵爿，其中 2 4 、 一 f ，1： g + ：乳 + p 西北工业大学硕士学位论文第三章带状线性方程组的交替方向去 a = 41 一l4一l 一l 一14 b t = c = 一f 右端项，= 取初始向量为 x 。= ( o0 o ) ，在 = 5 0 ，脚= 1 0 0 0 ，终止条件为占= 1 1 0 时，在h p r x 2 6 0 0 集群上进行并行测试( 计算时间以秒为单位) ，计算结果见下表1 。 4 = 篓三；圣ii l ； ，e = c = 一3 2 4 ，= ，在。，= i ， 所= 8 0 0 0 0 及终止条件为s = l x l 0 。o 时，在h pr x 2 6 0 0 集群上进行并行测试f 计算 例3 椭圆型偏微分方程 e 害+ q c y 矿a 2 u + ( qs i n 2 ；r x + g ) 罢+ ( d is i n 2 7 r y + d ： a 掣u + e u = 。 0 x y 1 和边界条件 ”u 。k = ；o 。：= “u l l ：，：= 1 1 。0 + + c c 傩o s 石l r z y ( 其中，e ，q ，c l ，c 2 ，d l ，d 2 和e 是常数) 分别取e = c v = e = 1 ，q = c 2 =