（计算数学专业论文）大型周期块三对角线性方程组的并行算法.pdf

丐止i 业八学坝：。沦殳 摘要 充分发挥并行计算机的潜在性能，寻求大型稀疏线性代数方程组的高效并行 解法，是当前大舰模科学计算中急待解决的问题，也是研究的热点问题，并行算 法设计与并行程序实现的关键：依据不同并行计算机的结构特征，减少整体通讯 并尽量使各处理机之间负载平衡 本文基于分布式存储环境，着重研究系数矩阵为大型周期块三对角的线性方 程组的并行求解问题，提出一些相应的高效分布式并行算法 主要完成了如下l 作： ( 1 ) 基于对系数矩阵的分解，根据分治思想提出了一种近似直接并行解法， 使算法只在相邻处理机涮有两次通信，有效地减少了通信次数从理论上， 给出了该算法成立的一个充分条件并在b pr x 2 6 0 0 集群上进行了数值计 算，验证了垓算法的有效性和可行性 ( 2 ) 在方法( 1 ) 的基础上导出了一种并行求解周期块三对角线性方程组的迭 代解法，通过对系数矩阵进行适当的分裂，促算法在不满足方法( 1 ) 的 条件下，也能够计算，即扩大了方法的使用范围从理论上，讨论了误差， 给出了系数矩阵为h e r m i t e 难定矩阵和m 一矩阵时算法的收敛性条件，最后 在t i pr x 2 6 0 0 集群上进行了数值计算验证 ( 3 ) 为加快方法( 2 ) 的收敛速度，引入松弛因子，得到一种松弛迭代并行 算法，虽然理论分析收敛性条件尚不完善，有待进步研究和探讨，但数 值算例结果表明，该方法具有很高的并行效率，且迭代次数大大减小，收 敛速度大幅度加快 ( 4 ) 提出了一种求解周期块三对角线性方程组的迭代并行算法，并给出了相关 的理论和数值算例 ( 5 ) 基于g a l e r k i n 原理，提出了一种求解块三对角线性方程组的a m o l d i 并行 算法，通过选取适当的予空间，使算法只在相邻处理机间有通信，因而具 有很好的并行性，而且证明了该算法的收敛性在h pr x 2 6 0 0 集群上进行 数值计算，结果莨明，加速比呈线性增加，并行效率达到9 0 以上 关键词并行算法，线性方程组，近似解，系数矩阵分解， a m o l d i 算法，h p r x 2 6 0 0 集群 一北业人学坝f j 论止 a b s t r a c t a tp r e s e n t ，ah o t s p o tp r o b l e mt ob es o l v e di st om a k et h eb e s tu s eo ft h ep o t e n t i a l c a p a b i l i t yo fp a r a l l e lc o m p u t e r sa n di n v e s t i g a t e sh i g he f f i c i e n tp a r a l l e lm e t h o d sf o r s o l v i n gl a r g es p a r s el i n e a rs y s t e m s t h ek e yp o i n tf o rd e s i g n i n go fp a r a l l e la l g o r i t h m s a n di m p l e m e n t a t i o no fp a r a l l e lp r o g r a m si st or e d u c eg l o b a lc o m m u n i c a t i o na n d m a i n t a i nl o a db a l a n c eb e t w e e np r o c e s s o r sa c c o r d i n gt oa r c h i t e c t u r ec h a r a c t e r so f d i f f e r e n tp a r a l l e lc o m p u t e r s b a s e do nt h ea b o v ei d e a ，w es l u d yp a r a l l e la l g o r i t h mf o rs o l v i n gp e r i o d i c a l b l o c k t r i d i a g o n a ll i n e a rs y s t e m so nd i s t r i b u l e dm e m o r ym u l t i - c o m p u t e r s t h em a i n r e s u l t so f t h i sr e s e a r c ha r ea sf o l l o w s ： ( 1 ) a na p p r o x i m a t ed i r e c tp a r a l l e ls o l v e rf o rp e r i o d i c a lb l o c k t r i d i a g o n a ls y s t e m so n d 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 r si sp r e s e n t e d t h ea l g o r i t h mi sb a s e do nt h e p r i n c i p l eo f d i v i d e a n d c o n q u e r a n dt h ef a c t o r i z a t i o no ft h ec o e f f i c i e n tm a t r i x ， i tm a k e sf u l lu s eo ft h e s p e c i a l s t r u c t u r eo ft h ec o e f f i c i e n tm a t r i x t h e c o m m u n i c a t i o ni s o n l yt w i c eb e t w e e nt h ea d j a c e n tp r o c e s s o r s i nt h e o r y ，t h i s p a p e rg i v e sa ne n o h g hc o n d i t i o na n dt h ee r r o ra n a l y s i sa b o u tt h i sa l g o r i t h m f i n a l l y ，s o m en u m e r i c a lr e s u l t so nh pr x 2 6 0 0c l u s t e rs h o wt h a tt h i sp a r a l l e l a l g o r i t h mi sf e a s i b l ea n de f f i c i e n t ( 2 ) a ni t e r a t i v ep a r a l l e l s o l v e rf o r p e r i o d i c a lb l o c k - t r i d i a g o n a ls y s t e m s o n d 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 r si sd e v e l o p e db ym e a n so ft h ef i r s tm e t h o d t h ea l g o r i t h mi sb a s e do us p l i t t i n gt h ec o e f f i c i e n tm a t r i x i tc a nb ec o m p u t e d u n d e rt h ec o n d i t i o n sw h e r et h ef i r s tm e t h o di su n i r e a s i b l e t h ec o m m u n i c a t i o ni s o n l yt w i c eb e t w e e nt h ea d j a c e n tp r o c e s s o r sp e ri t e r a t i o n i nt h e o r y ，w eg i v ea c o n v e r g e n tc o n d i t i o n sw h i c ht h ec o e f f i c i e n tm a t r i xi sh e r m i t ep o s i t i v ed e f i n i t eo r m m a t r i xa n dg i v et h ee r r o ra n a l y s i sa b o u tt h i sa l g o r i t h m f i n a l l y , s o m e n u m e r i c a lr e s u l t so i lt i pr x 2 6 0 0c l u s t e rs h o wt h a tp r a c t i c ec o m p u t i n gi s c o n s i s t e n tw i t ht h e o r y ( 3 ) w es t u d yar e l a x e di t e r a t i v ep a r a l l e lm e t h o d t h eg o a lo fi n t r o d u c i n gr e l a x e d f a c t o ri st oa c c e l e r a t et h ec o n v e r g e n c er a t e ad i f f i c u l t yi st oi n v e s t i g a t et h e a l g o r i t h m sc o n v e r g e n c e ，b u ts o m en u m e r i c a lr e s u l t so nh p r x 2 6 0 0c l u s t e rs h o w t h a tb o t ht h ei t e r a t i v en u m b e ra n dt i m ea r ef a rs m a l l ，t h ec o n v e r g e n c er a t ei s b e t t e r , t h ee f f i c i e n c yi sh i g h e r 两北j 业人学帧1 论置 ( 4 ) a na c c u r a t ep a r a l l e la l g o r i t h mm rs o l v i n gp e r i o d i c a lb l o c k t r i d i a g o n a ls y s t e m s o 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 r si sd e v e l o p e d m e a n w h i l e ，s o m er e l e v a n t t h e o r ya n dn u m e r i c a le x a m p l e si sp r o p o s e d ( 5 ) w ep r o p o s e dap a r a l l e la l g o r i t h m o fa r n o l d im e t h o db a s e do no a l e r k i n f o r m u l a t i o nf o rs o l v i n gb l o c kt r i d i a g o n a ll i n e a re q u a t i o n s b ym e a n so ft h e c h o i c eo fa p ts u b s p a c e so rm u l t i p l es e a r c hd i r e c t i o n s ，t h i sa l g o r i t h mo n l yr e q u i r e s t w oc o m m u n i c a t i o n sb e t w e e na d j a c e n tp r o c e s s o r sp e ri t e r a t i o n w ea l s og i v et h e c o n v e 唱e n c et h e o r yo ft h i sm e t h o da n ds o m er e l e v a n tn u m e r i c a le x a m p l e s t h e r e s u l t so fs o l i en u m e r i c a le x p e r i m e n t so nh pr x 2 6 0 0c l u s t e rs h o wt h a ts p e e d u p i m p r o v e sl i n e a r l ya n dt h ee f f i c i e n c yo ft h i sm e t h o di su pt o9 0 k e yw o r d s ：p a r a l l e la l g o r i t h m ，l i n e a rs y s t e m so fe q u a t i o n s ，a na p p r o x i m a t es o l u t i o n ， f a c t o r i z a t i o no f t h ec o e f f i c i e n tm a t r i x ，a r n o l d im e t h o d ，h pr x2 6 0 0c l u s t e l 两北1 _ 业大学硕士论文 第一聪钡斋缸i 只 1 1 引言 第一章预备知识 1 1 1 应用背景及并行研究的意义 许多大型科学与工程计算问题最后常需要解一个或些大型稀疏矩阵的线 性方程组本文所要讨论的是在数学物理及工程技术领域，如微分方程的求解、 多项式插值、网络、系统控制等方面常会碰到的大型、分块三对角矩阵为系数阵 的线性方程组的求解问题，山于现今科学研究与大型工程项目中各种复杂的计算 课题对计算机的要求越束越高，串行计算机已不能满足这一需求，而并行计算机 的出现便问题能够得以解决 受存储量和计算量的限制，解大型线性方程组目前常用迭代法并行计算，因 此并行求解大型线性方程组，要求算法既要有较高的并行度即算法适合并行性， 又要有较快的收敛速度如果迭代算法只是收敛速度很快但并行度低，或算法并 行度较高而收敛速度慢，则都将达不到较好的加速比虽然求解线性代数方程组 的数值计算方法已很成熟，而串行算法不能直接用于并行计算机所以，面向并 行计算环境研究大型稀疏线性方程组的高效并行算法显得尤为重要 1 1 2 并行算法的研究现状 ( 1 ) 基本迭代算法及并行改造 j a c o b i ，g a u s s s e i d e l 和s o r 迭代是求解线性方程组的几类基本的迭代方 法并行机的出现使人们能立刻注意到它们在捌有并行处理机性能上的显著差 别 j a c o b i 迭代因各个分量的修f 十臣互独立而具有十分明显的内在并行计算特 性其主要优点是方法简单，然而它并4 i 常是收敛的，收敛时速度常较慢在研 究如何提高收敛速度的基础上，】9 8 3 年，l i s s i r l i s 提出了并行j a c o b i 型方法， 西北丁业人学颂i 论文 掉一帚颅器她识 并讨论了它的收敛性胡家赣等把它推广到两参数的情形，称之为两参数并行 j a c o b i 型方法 对于6 a u s s s e i d e l 迭代，因充分利用上次求出的新值，可加快收敛速度， 一因为每次求值都要用到上次的新值，使它不容易并行 对于s o r 迭代法来浣，由于各分量的计算是逐个相关的，园此，一般认为s o r 迭代法不适合并行处理，其内在并行性远不如j a c o b i 迭代由于s o r 多用于有 限差分或有限元方法导致的大型稀疏方程组的求解因此，利用系数矩阵零元素 或非零元素的特殊分布，采用红黑或多色排序成为实现s o r 并行处理的有效途 径然而，如何找到合适的“彩色模板”并保持自然排序下的收敛速度却是一个 问题黎放”等对s o r 方法通过改造提出的向量化s o r 算法，在一定条件下具有 较好的并行化计算性能，后柬，吕全义在文献 3 4 中对b s o r 方法通过改进引 入加速因子和松弛因子，使收敛速度相同，但降低了迭代次数接着。崔喜宁。1 在此基础上，结合尸巨方法，将内迭代采用尸t 方法，使矩阵的分裂在一定程度 上有大的改进，使算法更具灵活性，并行效率也很高 以上几种基本迭代方法是进行并行迭代的基础，充分了解其并行再借鉴串行 算法进行并行程序设计，在这些基础上研究新的算法并重新获得快速的收敛速 度 ( 2 ) 共轭梯度法的研究及并行改造 共轭梯度法作为一种实用的迭代法可以充分利用矩阵的稀疏性不需预先估 计别的参数就可以计算，这点不像松弛法，另外每次迭代所需的计算，主要是 向量之f 自j 的运算，便于并行化，而共轭梯度法的收敛速度和系数矩阵的条件数紧 密相关，条件数愈小，收敛性愈好，理论上，该算法可以在很少的几步内就会获 得高精度的近似解，但当系数矩阵的条件数很大时，收敛速度就很慢，为加快收 敛速度，通过预处理技术降低系数矩阵的条件数目前预处理技术方法( 简称 p c g 方法) 主要有j a c o b i 迭代预处理，g a u s s s e i d e l 迭代预处理，不完全 c h o l e s k y 分解预处理”1 等，张宝琳等对这些并行实现做了详细的描述 p c g 方法并行化的难点”3 在于预条件子的并行化和整体内积的计算，后者的 规约运算与广播都需要全局通讯，对大规模并行计算机尤为突出，己成为此类方 法大规模并行求解的瓶颈问题目f i i 已有一嗤方法来降低整体内积的开销，如重 西北r 业犬学颤 “论文 第一帚颅备盖h 供 叠训算与通讯”1 “1 以及将内积分组计算以减少通讯次数或同步点个数。，但 部无法完全逾越整体内积块共轭梯度法可更好地并行化，但需要更多的计算量， 一娄多搜索方向共轭梯度法1 ，它基于“：于区域”或未知量的划分，在每步迭代 中每个子区域都有一个搜索方向，相应r 其它于区域的分量为零，整体内积的计 算为求解小方程组所替代，这个小方程组的结构基于区域分解及搜索方向的选 取，f 叮用直接法或迭代法求解( j a c o b i ，g a u s s s e i d e l 迭代法) ，浚近似方法无 需整体内积丽仅需要相邻处理机的通讯，运算量高于共轭梯度法，但具有更好的 并行性文献 1 4 给出了对称- f 定问题多搜索方向共轭梯度法的收敛性理论；烙 志刚在他的博士论文。”中对此给出了更详细的研究和讨论，本文将合理运用和改 进此思想并结合a r n o l d i 方法，着重研究求解块三对角线性方程组的有效并行求 解，并给出该算法的一个收敛性定理 ( 3 ) 并行多分裂法的研究现状 好的并行算法要求各处理机的运算具有运算无关性，即并行性要好，要尽量 减少通讯量和同步开销基于此要求，1 9 8 5 年，0 l e a f y 和w h i t e 提出多分 裂并行选代法，它被认为是一类重要的并行数值方法近年来引起了数值计算工 作者的极大兴趣，进一步改进了其算法模型，完善了收敛理论而异步迭代并行 算法也是随多处理机的出现而发展起来的一类新的算法1 9 6 9 年，c h a z a n 和 m i r a n k e r 首先提出，目的在于减少处理机的通信与同步，提高各处理机的利用 率后来又被许多学者以不同的方式在研究这里介绍多分裂法的一些概念 求解大型线性方程组 a x = 6 其中，a 是n n 的非奇异矩阵 令m ，_ r ，和层，都是n n 矩阵( ，= 1 , 2 ，a ) 口足大于零的正整数，若满足 ( 1 ) a = m ，一n ；，m f 非奇异 ( 2 ) e ，= ，( 1 为n x 单位矩阵) ，f ，是非负对角矩阵 = l 则称三元组( m ，n ，e ，) ( ，= 1 , 2 ，口) 为a 的一个多分裂 算法1 ( 多分裂迭代法) 西北r 业人学顺i j 论立第一母预箭知识 任取初始近似x r 。，对k = o 1 ，2 ，重复做下面的( 1 ) 、( 2 ) 两步，直 到收敛 ( 1 ) 对z = 1 , 2 ，口，求解y 。 m ，y f = n ，x ( 。+ b ( 2 ) 计算 工耻“k e f y f ，= 1 进一步分裂矩阵m 为 m t = f t g t 这样就产生了二阶多分裂迭代法 算法2 ( 非定常二级多分裂迭代法) 任给初始向量x ，对k = 1 , 2 ，直到收敛 诗 z = 1 , 2 ，一，瑾 ej j = g 7 y i ，一f + n ，x 一l + 6 ( 1 1 ) 以= e y 刖，女 当j ( f ，七) zs 为固定数时，在每个外迭代步中，各处理机的内迭代步数均相同， 此时称为定常二级多分裂迭代法，记作s t s m 迭代法；此方法是由s z y l d 和j o n e s “” 于1 9 9 2 年提出的，他们证明了当月为单调矩阵，且内外分裂为特定的分裂时， 方法对任意内迭代数s 1 均是收敛的谷同祥和刘兴平将此推广到任意次数的二 级多分裂迭代( n s t s m 迭代法) “”，同时又进行异步化和松弛化，还在理论上证 明了松弛因子c o 的取值范围为0 0 成立，则称a 为h e r m i t e 正定矩阵 定义1 2 ”p - 正则分裂# 设矩阵a 是n 阶方阵，若矩阵脚和满足： 爿：m 一且m “+ r 为h e r m i t e 币定矩阵，则称a = m n 为a 的p 一正则分 裂 引理1 1 m 1 若a 为实对称f 定矩阵，则爿= m n 是p - 正则分裂充要条件 是l m 。j j 、r 虬 0 时，称a 为i f 矩阼 定义1 4 “”若一个门阶实矩阵的逆矩阵a “0 ，则称a 为单调矩阵 定义1 5 ”“设爿为v 7 的矩阵，称分裂a = m 一为 ( 1 ) 正规分裂，如果m “0 ，n2 0 ； ( 2 ) 弱正规分裂，如果m - 1 0 ，m 。n 0 ，n m “0 ： ( 3 ) 第一类弱非负分裂，如果m 1 0 ，m 。1 n 0 ； ( 4 ) 第二类弱非负分裂，如果m “0 ，n m “0 引理1 2 1 设a r ”，a = m 一为矩阵爿的弱氘规分裂( 第一类弱非 负分裂) 或正规分裂，则p ( m 1 i v ) 1 当且仅当a 。2 0 引理1 3 1 设a r “”且a “0 ，a = m n 为矩阵a 的第二类弱非负分 裂，则p ( 肘。) 1 引理1 4 2 设a = m n ，且爿和m 都可逆，则对m 。n 的任意特征值， 存在爿。的某个特征值五，使得= 害j 3 l 理- 1 5 1 若a = m n 为矩阵a 的正规分裂，且一。0 ，则 p ( m i ) = p ( a - n ) ( + p ( ) 从而p ( m 一2 i v ) 0 ( f = t , 2 ，n ) ，且b = i d 。a 满足p ( 曰) 1 ，这罩 d = d i a g ( a ，d 。) 。 性质5 设a 为m 一矩阵，当4 的任意元素( 一个或多个) 增大时，但保持主 对角线外的元素仍然为非正值时，则所得的矩阵也是m 一矩阵，且有“a 性质6 矩赡a = ( 日。) 为m 一矩阵的充要条件是存在正数s 使得爿= s i - b t 其中b 0 b 的谱半径妒( 丑) s 性质7 设矩阵a = ( 口。) 为z 一型矩阵，并且有三角分解式a = c ，其中l 和，分别是下三角m 一矩阵和上三角m 一矩阵，则a 为m 一矩阵 性质8 设矩阵a = ( 口。) 为z - 型矩阵，且它的门个顺序主子式均为正值， 则4 必有三角分解a = l u ，其中工和u 分别是下三角 i 矩阵和上三角j i i 一矩阵 性质9 设a 为m 一矩阵，则它的订个顺序主子矩阵都是m 一矩阵 性质1 0 发爿为z 一型矩阵，则a 为m - 矩阵的充要条件是a 的疗个顺序主子式 均为正值 堕苎工些查兰竺! ：堡兰 星= ：! 塑塑堡三翌堡垡竺变堡些堕二堂皇! ! ! ! 塑 第二章周期块三对角线性方程组的一种直接解法 本章提出了一种求解系数矩阵为周期块三对角线性方程组的适合于m i m d 分 布式存储的并行算法，该算法以系数矩阵分解为基础，充分利用系数矩阵结构的 特殊性，进行近似处理，使整个的计算过程只在相邻处理机削通信两次，具有很 好的并行性，并从理论上给出了该算法成立的充分条件，分析了误差最后，在 h pr x 2 6 0 0 集群上进行数值试验结果表明，当方程组的阶数足够大时，加速比 呈线性增加，并行效率达到8 0 以上 2 1 算法推导 b c 骥al ， 。j l = 巨 ( 2 1 ) 这罩a ，足n ，阶方阵，b ，和c ，分别是疗；行。和n 一一。矩阵- b m 和c 1 分别是 h 。”和n n 。，矩阵，x ，均为n ，维列向量- 假设处理机台数为p ，记第f 台处理机为p ( f _ 1 ，p ) ，设 川：肚( t 2 ，z ) ，将4 分解成两矩阵的乘积 r d ， f t h g l a = f t = t n 6 2 o 誓 1 2 ) p 一1 。，j l z ，；，一1 i 。；r - ，iu ，p ，_ i 9 ( 2 2 ) 西北业人学硕l ：论史 旃一即j 州j l 】块= 对确线叶7 j 程组的一种直接m ，土 右端项，及未知向量x 小作相应划分，即f = 旧，巧y ，x = 伍i ，x j ) t 这罩 d= a i ，一 “b “一【) + 1 c h 她2月( _ l m 2曩h m 2 c * 一la ? k 一、b c | k a t 1 为( 喜 。一。： ( 妻”。，；，。+ 、) 的单一立* n s 车，h ，为( 喜n 。，一，。+ 、1 x ( 喜n 。+ 。) 。矩 为【 卜m 。：h 飞，娟。；的单位矩阵，为 n t 一灿、i x i + 。j 的矩 = l = i ，= i = l 阵，只有最左边的，列元素非零( h ，为l n ( 川卅，i x k j 的矩阵，只有最左 t 、， 、 ，= il = l， 边的列元素非零) ，设其最左边的 。列元素为l 】i ( ，) t ，) t ) t ： g f 为 f 圭。1 。f 壹圳。1 的矩阵，只有最右边的_ ”。列元素非零( g ，为 | n ( 。卅，i i _ 。灿。 的矩阵，只有最右边的胛( “) t 列元素非零( ，为 一= is = l f 圭怫1 。f 杰订( ，州。1 的矩阵，只有最右边的列元素非零) ，设其最右边的 5 1一= l 代。列元素为昭 ) ) t ， ，露( ，= l ，) 分别是n t + ，n 。和 ”呲+ ，胛( h 坤矩阵，且满足下列方程组 4 h ) 曰m c ( 吣+ 24 h m + 2 曩h 1 m c * i f z ， l i 雹一 b 。| lz 怂 爿。lz q 手 d ( 2 3 ) ( 2 4 ) 对方程组( 2 3 ) 的增广矩阵进行初等变换，消去主对角线以下元素，再利 ；啦 viiiiii一 以以e _ 雌、协 艮 c n ” “ n 呲嘶 4 q 两北t 业人学坝卜葩芷 用赶的过程求得方程组( 2 3 ) 的解为 其r f 堕= 垦型型些三型塑垡壁塑堡坐塑二塑皇堡塑堕 掣：( 一1 ) “a 仁柚。+ ，) ( j ：，1 ) ( 2 5 ) j l h ) m = a ”l 】 b a 叫叫= 钆m ，一c ，七) 同理，对方程组( 2 4 ) 的增广矩阵进行初等变换，消去主对角线以上元素， 再利用追的过程求得方程组( 2 d ) 的解为： 其中 z = ( 1 ) 川n ( 缸呲+ 、c ( i - l l k + s ) ( - ，= 1 ，t ) ( 2 6 ) 挣2 a , k ( j ：，1 ) 【一( h m j = a ”+ 厂b ( h ) 爿( ：l c m 川 将矩阵4 分解成式( 2 2 ) 以后，方程组( 2 1 ) 的求解等价于求解 这肇 t = ， x ( 9 ) m 】：n 玎” f u = f 孤= “ z 出 4 ” e 2 j 2 + l z 1 ： 乏： z ：” ( 2 7 ) ( 2 8 ) 两北丁业太学坝i 。论史 第一母埔期块= 对角线性方程组的一种且接解法 显然，求解方程纽( 2 7 ) 是一个并行求解过程，而确定，和g 只需求解式 ( 2 3 ) 和式( 2 4 ) ，这两个方程组的求解从式( 2 2 ) 可以看出也是个并行求 解的过程，但在求解式( 2 8 ) 时圉各处理机之间要相互传递数据而使并行性降 低，为提高其并行性，现给f 一个扰动? a t = i 瓦l 。 ( 2 9 ) 其中为珂阶方阵，墨j i k 扎水+ l = 一v ( = l ，一，p i ) ，五f 一。) 女扎。= 一鬈， t 一 = 一z p l ( = 2 ，p ) ，瓦，肚= 一z ：1 ) 其它予块均为零矩阵，写成矩阵 的形式即为： t = d k 0 ： d 可通过解方程组 0 0 ： d 一五2 00 00 ： 0 4 ” ： 0 ； 0 一z p ( f + a r ) ( x + a x ) = ( 2 1 0 ) 来近似代替解式( 2 8 ) ，其中x 满足t x = ，而式( 2 1 0 ) 具有很好的并行性 只需相邻处理机之间进行两次数据传递，有效减少了通信次数 酽d k d ，d d 两北工业犬学硕i ：论义 第一章l 州期块二对角线性方程纽的一种直接解法 2 2 并行实现 2 2 1 存储过程 将a ( - l 肌，b ( f _ i 卅，c i 。灿，以及右端项。m ，( = 1 ，七) 分配到第i 台处 理机只( i = 1 ，p ) 2 2 2 计算过程 ( 1 ) 在尸( f - 1 ，p ) 台处理机上并行求解式( 2 3 ) 、式( 2 4 ) 和式( 2 7 ) 得到忆。，) t ，懈，) ) t y ，( ( z 坩，愀) ) t y 和陋y ) t ，p ) t ) t ( 2 ) 鼻台处理机将z p ，“1 传给匕台处理机；f ( f = 2 ，p ) 台处理机 将z ：“，u ：叫专给尸一台处理机； ( 3 ) p ( i = 1 ，p 一1 ) 计算求解方程组 ( z 。 并将x 1 7 的值传递给尸小在只中计算求解方程组 并将x ? 1 的值传递给弓 ( 4 ) 在只中计算 x ：1 ) - 【，p 一垆x ：”一z ，搿1 ( ，= 2 ，k 一1 ) 在p ( i = 2 ，p 一1 ) 中计算 在只中计算 x ：o = ，：”一_ o 工 ”一z ：“x ：” ( ，22 ，七一1 ) ， 0 汁 研 ， | i 0， j 什 x 0v 0 。0 八 曙， 蚪叫 ，。 i l 、l 掣掣v i 0 几 引， 西北r 业人学坝l ：论文 赫一肇嗣j 螗块二礼角线性方程组的种q 接斛法 x 押j = u y l y j x “一z 坤1 ”。( ，= 2 ，七一1 ) 得到方程组( 2 1 0 ) 的解 可以看出，本算法只在计算过程中需要相邻处理机之间通信两次，因而具有 很好的并行性和可扩展性，很适合在m i 分粕式存储环境下进行并行计算 注若m 不能被p 糕除，则一些处理机按顺序存b7 p 】+ 1 行块，j 一些存b p 】个 行块，同时将薯，中相席的向量存入对应的处理机中，达到处理机的负载人体均衡，以 减少等待时间以后备章钳都采川这种处理方式 2 3 误差分析 算法的关键是系数矩阵a 在满足什么条件时方程组( 2 1 0 ) 可代替方程组( 2 8 ) 进行近似求解，在此我们讨论算法可行需满足的条件 由式( 2 9 ) 可知忪r 虬= 聊掣0 砰“k 9 乏。1 虬) ，方程组( 2 i 0 ) 的近似解与 方程组( 2 8 ) 的精确解的相对误差满足不等式”“ 瞥掣盘铬 亿 两s 司司面币瓦 “ 显然恰f 忆越小，精度越高，即坍哆0 x j 虬，| | 墨叫。) 越小，精度越高 定理2 3 1 若4 。非奇异，对给定的正常数，( ，= i ，2 ，3 ) ，使得忙。一b 。k k 时，有 m 哆0 x ”虬，1 1 z ：n 忆) 占 ( ，= 1 ，p ) 证明：由k 。1 的表达式( 2 5 ) 知，先证睁? e 虬 f 鲁，这里我们采用数学 归纳法证明 两北 业人学倾， 论文 塑：二：! 塑塑鉴j 苎塑竺堡塑堡垡堕二塾坚堡! 堡 呲啪。砘q 2 ) 时r = r j i 仑a , ! ，甄，虬 f 蠹成立 由已知和假设知 她- i c 叫a 。- i c k 州p 叫：南 从而 l l j ：1 占。k = i l c 4 。一c 。爿- - “1 占。) _ 1 蛾k = 卜钉坼! t “a k - b k 虬 s 插 上 上 1 一z 2 f 1 + 1 3 故，对v f z ，结论忙i 1 置8 。 。，存在k 。= 五彘 ，对任意的 磷 i“仉寸 一 ” 一+ h 一堪 k 2 ，有 峪忆 0 ，存在k = m a x 区。，k ：) n ，对任意的七 k ，有 卅黟忡忆粉 o ) 岩 且窆k i ，则当n - o o 时，有卜；i - - o ( 1 f 蔓) 爿 ( 1 k 兰，一1 ) 证明：设增广矩阵( 4 j p 。) 进行行初等变换后得到( a i q 。) ，其中a 如引理 2 1 所示 设上= m a x l ，+ ， ( r = ，) 下证l 磉。l 兰l - ( 瓦惫) 1 ( m = o ，- ，) 用数学归纳法显然m = 0 成立 假设m ：s o 1 ) 时，结论成立，即卜：。4 s 三一( 高) ( f = 1 ，) 下证坍= s + 1 时，结论成立 1石：一。+，+，l!：ii；j：-：ii：忑(鬈一an-(x1l+tn-v+-1)l+,+jx：一。，+tv+，+，l 臣磊三习。阱- 2 _ 州“”m 一川屯一删i 而三习倍呻圳m 州“灿w j ) ( 彘) 5 乜 根据引理2 1 ，我们有 西1 b t 业火学烦士论文 第一章粥j f 块三对舟线性方程组的一种苴接解法 。川熹 ”1 故，对任意的脚 0 ) ，结论都成立 于是，当”斗0 。时，要使摊一m l + f j t ，只有m o o 。即当盯一时，有 ( 1sr 女) ( 1 k 兰，一1 ) | | 证毕 对方程组a x = b ， b = a n - t n - j p “+ + 吼，j e n ( 1 七，一1 ) 的解 x ：圭a 。一，x 。，其中4 托一，= 气一，( f = 0 ，) 根据定理2 3 2 ，当n 。时， 怫一。l 斗o 令m ，= m a x t g - , , - j 卜，l q n , n - j m 则当胛j 。时，方程组血= 6 的解 的第胛一f 个分量 k ，1 = k 一，+ ( ，n - l , n - y x ：口n , n - y x ：一j m 。慨，卜+ 睇；+ 陋t ) - ，o ( 1 k 1 一i ) 同理，当”一时，方程组a x = b ，b = a j - k e i + + a j , n - k 气( 1 ，k s l 1 ) 的 解的第i 个分重k i 寸0 ( 一1 十1 j s ) 显然，从实用的角度看，定理2 3 2 更实用 定理2 3 3 在满足定理2 3 。l 的条件下，对任意给定的s 0 ，当 t 竺三i 辫+ t 时，方程组c z t 。，的解满足式 铬“ 隰 。一 证明：由式( 2 1 1 ) 知 l 。，f i t - r l l i 善虬二1 一i ，一l 。 b 丁 。 为满足式( 2 1 2 ) ，需使上式右边小于s ，有 蚓卜去赢 两北工业人学坝f 论史 蚺一矗川姗址二对角线忡方程封l 的一种直接衅法 由定理2 3 1 的证明过程，则 忪r 忆 ( 划， 七 在这罩不妨假设m a x ( 焘h 南 1 ：( 矧，因而只要 焘 。 女 些! 些茎塑! ：堡兰 一苎望型螋塑些坚堕堂丝 爿。： ! j ： ，。：，露，= ( 一20 2 1 。：，c 2 ( j 3 。： 右端项，：( 3 ，o ，l ，1 3 ，2 ) ：，曰。= c 。= d 显然爿，可逆，归_ 曰。虬。茜 1 忙i t c ，忆= 1 7 1 。 1 ，当t l a r l l 。= m 尹4 e 圳。，0 z p 4 。) = 1 - 一1 5 时，需2 1 1 0 现 取方程组的阶数h ：5 0 0 ，在 pr x 2 6 0 0 集群上进行并行测试( 计算时瞄以秒为单 位) ，其结果见表2 1 ，取n = 5 0 0 0 0 0 计算结果见表2 2 ： 搠12 对于系数矩阵 簪 曰，：c ：一，右端项，= ( 1 ，1 ，1 ) ：1 在聊= 2 0 0 0 0 ，t = 5 0 m , 用m a 1 a 6 6 5 1 计算1 4 j - 1 曰，k = 1 4 c ，虬= o 5 ，并行求解的结桑见表2 3 和表2 4 例3 对于形如例2 的m 一矩阵4 ，取 4 ：l 二1 毒5 1 j - ：3 主- 6 9 1 4 , 8 ，b ，：c ，：f 一3 2 一。 ，：= 1 ，月。= g 2 。一 4 2 l 二毒j ：i ： b f = c 1 2 l 一2 一。j ：2 l ：j 毋= g 2 。 当m ：8 0 0 0 0，用l ；f l a t l a b 6 5