（应用数学专业论文）解大型稀疏线性方程组的整体松弛并行多分裂法.pdf

a b s t r a c t i nt h i sp a p e r ，w ec o n g i d e rt h e 出o b a lr e l a x e d ( n o n s 七a t i o n a r y ) p a r a n e lm u l t i s p l i 七t j n g ( m u l t i p a r a m e t e r ) t o ri t e r a t i v em e t h o d sf o rs o l v i i 培l i n e a rs y s t e m so fa l g e b r a i ce q u a t i o n 8 a x = b ，o u rm e t h o d su s es e v e r a lr e l a x e df a c t o r s ，c a v e rw i t hm a n yp a r a l l e lm u l t i s p i i t t i n g i t e r a t i v em e t h o d si nt h el i t e r a t u r e ，a n dh a v ea l l - r i g h tu n i v e r s 出i t yt h ep a p e rc o m p a r e s t h ec o n v e r g e n ta n dd i v e r g e n tr a t e so fp ”a l l e lm u l t i s p l i t t i n gr e l a x e dm e t h o d si n d e t a i l - f 、l r t h e r m o r e ，e 伍c i e n c y0 ft h eg l o b a lr e l a x e dm e t h o da r es h o w nb yn u m e r i c a le x p e r i m e n t i n m p p i nc h a p t e ro n e ，w eg i v ead e t 缸l e dr e v i e wf o rt h ep r e v i o u sw o r ko nt h es u b j e c t ，i n c l u d i n g b a c i 曜，o u n da n dd e 、伧l o p m e n ts i t u a t i o n i nc h a p t e rt w o ，l o c a lr e l 弧e dp a r a u e li n u l t i s p l i t t i n gt o ri t e r a t i v em e t h o da n dg l o b a l r e l a x e dp a r a l l e lm u l t i s p i i t t i n ga o r ，s o ra n dt o ri t e r a t i v em e t h o da r es t u d i e d ，c o m p a r i s o n so fc o n v e r g e n ta n dd i v e r g e n tr a t e so fp a r 越l e lm u l t i s p l i t t i l 培r e l a x e dm e t h o d sa r e g i v e ni nd e t a i l n u m e r i c a le x p e r i m e n ti u u s t r a t e st h ee 伍c i e n c yo fo u rm e t h o d s i nc h a p t e rt h r e e ，w es t u d yn o n b t a t i o n a r ym u l t i s p l i t t i n gm u l t i _ p a r a m e t e rt o ri t e r a t i v e m e t h o da 丑dg l o b a lr e l a x e dn o n s t a t i o n a r yr n u l t i s p h t t i n gm u l t i p a r a m e t e rt o ri t e r a t i v e m e t h o d ，a n dc o m p a 糟t h ec o l l v e r g e n ta n dd i v e r g e n tr a t e so fn o n s t a t i o n 盯ym u l t i s p l i t t i i l g i n u l t i p 盯a m e t e rt o r ，a o r ，s o r ，g a u s 8 - s e i d e l ，e 吼r a p o l a t e dj a c o b ia sw e l la sj a c o b i i t e r a t i v em e t h o d si nd e t a i l n u m e r i c a le x p e r i m e n tm u s t r a t e st h ee m c i e n c yo fo u rm e t h o d s i nc h a p t e rf o l l r ，w es t u d yp 耻a l l e l m l t i s p l i t t i n g8 y m m e t r i ct o ri t e r a t i v em e h t o d ( s t o r ) a n dp 盯a 1 1 e 1m 1 1 1 t i s p l i t t i n gu n s y m m e t r i ct o r i t e r a t i v em e h t o d ( u s t o r ) f o rs 0 1 v i n gl i n e a rs y s t 眦so fa l g e b r 缸ce q u a t i o n sa ) 【= b ，c o l p a r et h ec o r i v e r g e n ta n dd i v e r g e n t r a t e so ft h e 8 em e t h o d sa n dp a r a l l e l 咖l t i s p l i t t i n gj o ri t e r a t i v em e t h o d ， i nc h a p t e rf l v e ，w e 印p l yg l o b a lr e l a x e dp a r 出l e lh m l t i s p l i t t i n gi t e r a t 溉l e t h o dt o n o n l i n e a re q u a t i o n s ，c o n s t r u c ta n d8 t u d yt h en e w t o n _ g l o b a lr e l a 翮dp a r a l l e lm u l t i s p l i t l l 第一章引言 c a o 【1 2 ，1 6 等对二级多分裂也进行了深入的研究；l i 1 7 1 构造和研究了解非线性方程组 的牛顿一并行矩阵多分裂算法，建立了收敛性定理，估计了收敛速度总之，关于多分裂 的研究及结果如雨后春笋般出现本文研究的是求解线性代数方程组a z = 6 的整体松弛 ( 非定常) 并行多分裂( 多参数) 迭代法，通过选用多个松弛因子，我们的方法覆盖了许多 文献中已见的并行多分裂迭代法，具有很强的普遍性本文详细地比较了并行多分裂之间 的敛散速度，并在一台m p p 并行机上进行多次试验大量的数值试验表明：我们的方法 确实对文献的方法进行了有效的改进 3 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 2 1 整体松弛s o r 方法 许多大型科学与工程计算问题最终归结为求解线性代数方程组 a z = 6 ( 2 1 1 ) 其中4 丑”“是非奇异矩阵，妒为待求解向量，且设，为( 2 1 1 ) 的解 定义2 1 1 令地：肌，风均是矩阵，= l ，2 ，若满足 o ) 4 = 尬一 k ，n 行1 存在 取= ( j 为单位矩阵) ，岛是非负对角矩阵 则称三元组( 慨，肌，西) ( = l ，2 ，o ) 为矩阵a 的一个多分裂 方程组( 2 1 1 ) 可以写成 z = 峰1 。+ 螈1 6 ，= 1 ，2 ， 用权矩阵鼠组合这n 个方程，得到 z ( 研+ 1 ) = h 茁巩) + g bm = 01 称为多分裂迭代格式口称为多分裂迭代法的迭代矩阵，其算法如下 算法1 ( 并行多分裂方法) 任取初始近似z ( o ) 冗” 对m = o ，1 ，重复下面的i ) j i ) 两步，直到收敛 i ) 对= 1 ，2 ，n ，( 并行) 求解玑 i ) 对= l ，2 ，n ( 并行) 求解鲰 a 靠= z ( m ) + b( 2 l2 ) + z盯 一 b k m 玩 。m + z 帆悔& 。m z 酞 。m z k m 研 。 = gm 。 壮黻中代 其迭 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 5 i i ) 计算 。( ”+ 1 ) = f 最靴( 2 1 3 ) k = l 我们看到，在( 2 1 2 ) 中每个玑的计算是相互独立的因此，若有一台具有一个主机 与个处理机的并行机，则算法1 可这样实现：每台处理机处理一个局部迭代( 2 1 2 ) ，在 每一步，将局部迭代值弛( 七= 1 ，2 ，口) 送到主机进行加权平均而得到整体迭代值z ( ”+ ”， 即( 2 1 ，3 ) 的计算然后将z ( + 1 ) 送回各处理机以开始下一步局部迭代注意到如果取 的某些对角元素为零，则瓠的相应分量无需计算，从而大大节省工作量由此可见也 起到调配各处理机上工作量的作用我们应尽量选择b 使得各处理机间大致做到负载平 衡，从而减少同步等待的开销可见，算法1 具有自然的并行性 定义2 1 2 4 = ( 血“) r 。，z 。= a r 。v 。i a i j o ，b 乍j ) ( 1 ) 若o ，i ，j 一1 ，2 ，n ，则称a 为非负矩阵，并表示为a o ；记 a i = ( 1 嵇 ) ； 若a b 0 ，则表示为a b ； ( 2 ) a 的比较矩阵为( a ) = ( o 玎) ，其中 j 时，n 玎= 一陋柑l ；i = j 时= l o 玎| ； ( 3 ) 若a z 。且a 一1 o ，称a 为m 矩阵； ( 4 ) 若似) 为m 矩阵，称a 为日矩阵 引理2 1 3 【1 8 若a ，b 月。，d = d n 9 ( a ) ( n ) 若a 是m 矩阵，则d o ，且d 非奇异； ( 6 ) 若a 是m 矩阵，_ b z ，且asb ，则b 是m 矩阵； ( c ) 若a 是h 矩阵，则a 非奇异，且l 4 l - 1 ( a ) _ 1 ； ( d ) 已知a ，b 均是m 矩阵，若a b ，则a - 12b - 1 ； ( e ) 若a 是日矩阵，且a = d 一日，则d 非奇异，且p ( 1 d i - 1 l b i ) 1 为了提高算法的收敛速度，与传统的g s 迭代法引入松弛因子而得s o r 迭代法类 似，通过对算法l 引入松弛因子，3 给出了两种松弛型多分裂迭代法：其一是局部松弛 法，即各处理机用s o r 方法求解( 2 1 2 ) ，而( 2 1 3 ) 的计算依旧；其二是系统松弛法，即 ( 2 1 2 ) 的计算依旧，而对( 2 1 3 ) 进行松弛外推适当选取松弛因子，两种松弛型多分裂 方法都比原方法( 算法1 ) 具有更好的收敛速度本节考虑将两者进行结合，即对( 2 1 2 ) 和( 2 1 3 ) 均进行松弛，所得方法称为整体松弛并行多分裂法，下面给出两种权方案下的 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 6 整体松弛s o r 方法由多分裂格式可得 从而，算法1 也可写为 h = i g a z ( ”+ 1 ) = ( j g a ) z ( ”) + g 6 ，m = o ，1 ，2 ， ( 2 1 4 ) 对此迭代格式加以推广，引进 其中0 a 1 ，相应的迭代格式为 z ( m + 1 ) = h z ( m ) + g 6 ，七= 0 ，1 ，2 ( 2 1 5 ) ( 2 1 6 ) 迭代格式( 2 1 6 ) 称为具有任意权方案的多分裂迭代格式，其中a = 1 时，称为左权 格式，即原来的迭代格式；a = o 时，称为右权格式；a = l 2 时，称为对称权格式令 a = d 一三一巩，南= 1 ，2 ，o ， 其中d = 击。9 ( j 4 ) ，k 为严格下三角矩阵，则( d k ，巩，取) 为a 的一个多分裂 算法2( 左权整体松弛并行多分裂s o r 方法( l e f tg l o b a lr e l a 】【e dm u l t i s p l i t t i n g s o r ) ，简记为l g i t m s o r 方法) 任取初始近似。( o ) r 对m = o ，1 ，重复做下面的i ) i i ) 两步，直到收敛 i ) 对= 1 ，2 ，a ，( 并行) 求解弧 ( d u 1 l k ) 可= 【( 1 一u 1 ) d + u 1 巩 。( “+ u 1 6 ( 局部松弛) i i ) 计算 z ( ”+ 1 ) = u 2 b 弧+ ( 1 一u 2 ) z ( ( 系统松弛) 此算法可写成下面的形式 z ”- 1 = 乩z ( ”) + g 。6 ，m = o ，1 f 2 1 7 、 ag 一 = 日 。 硪峰硪 。脚 | | g 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 7 其中 d 风= 甄( d u 1 l ) 一1 ( 1 一u 2 ) ( d u 1 三七) + u 2 ( 1 一u 1 ) d + u 1 巩 ) = 1 当u 。= 1 时，即得 3 的局部松弛并行多分裂s o r 方法：当u ，= 1 时得【3 】的系统 松弛并行多分裂方法可见，l g r m s o r 方法是局部松弛并行多分裂s o r 法和系统松 弛并行多分裂方法的推广，其中我们选用了两个松弛因子可以期望通过适当的选择松弛 因子，能得到更快的收敛速度 关于l g r m s o r 方法，我们证明如下的收敛性定理 定理2 1 4 设a 为h 矩阵，对七= 1 ，2 ，a ，饥为严格下三角阵，a = d 一一仉， 且i a i = i d l l “i l 巩| 如果 o u ， 南脉u 。 赢， ( 2 _ 1 - 8 ) 则l g r m s o r 方法对任意初始近似z ( o ) 均收敛到，其中儿。= 1 1 一u 1 i + u l p ，p = p ( ，) ， 而l ，= l d i 一1 i b i ，b = d a ， 证明：因为p ( h “，) 曼p ( i 鼠。i ) ，故只需在定理条件下证明p ( 1 珏。i ) 1 由于 凰= b ( d u - l ) 一1 ( 1 一u 。) ( d u l k ) + u z ( 1 一u ) d + u 巩】 = 1 从而 i 风l 1 1 一u 2 i ，+ u 2 甄l ( d 一“1 l ) 一1j ( 1 1 一u 1 i d i + u 1 i 巩i ) k = 1 因为d u ，如是日矩阵，由引理2 1 3 ( c ) 知i ( d u 反) _ 1 | ( d u t 厶) ，所以 乩i 1 1 一u 2 i ，+ u 2 颤d u ，如) _ 1 ( 1 1 一u - 恻+ u 吲) k = 1 而a = d l k 一巩= d b ，故 d l ，= l “l + l 巩 第二章整体松弛并行多分裂t o r 法及敛散速度咝较9 定理2 1 7 设a 为日矩阵，对七= 1 ，2 ，q ，“为严格下三角矩阵，a = d 一一巩 且( 4 ) = d l l k i l 魄r 如果 22 o u 1 币，o “2 再面 则r g r m s o r 方法对任意初始近似口( o ) 均收敛到矿，其中阢，= l u 1 i + u 1p ，j 。= p ( ，) 而l ，= l d l 。l b l ，b = d a 证明：由算法2知rgrmsor方法的迭代矩阵为 曰。=芝二(dutl)一1(1一u。)(du，l)+叫2(1一u1)d+u-巩)西因为，( 鼠) s p ( i 鼠j ) ，故只需在定理条件下证明p ( 鼠i ) 1 l 由。i 1 1 一u 2 l ，+ u 2 | ( d u ，l ) 一1 l ( 1 l u | d l + u l f 仉j ) 风 七=l d1 1 一u 2 j，+u2(dullk)一1(ilullidl+ull仉i)最 k=1 s1 1 一u 2 l ，+ u 2 l d u 1 l k r _ 1 【l d u 1 l 七i + ( 1 1 一u l l 1 ) l d l + u l i d l j i 取 七=l= j 1 一u 2 i ，+ u 2 j u 2 ( d u 1 三) 一1 i d j ( 1 一1 1 一u 1 i ) ，一u 1 卅e k k=11 1 一u 2 l ，+ u 2 j u 2 ( j d u 1 三 ) 一1 1 d 1 【( 1 一l l u 1 1 ) j u l ( j + e e e t ) 巨 两边同时乘以札可得 l 鼠j 1 一u 2 z 。+ u 2 z 。一u 2 i d r _ 1 i d i ( 1 一1 1 一u l l u 1 风) z 。毋 k = l = i l u 2 z 。+ “2 ( 1 1 一u l i + u 1 风) 文 从而当满足定理条件时，就有l 鼠k 欧，故 p ( 1 也1 ) 1 定理得证 口 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 证明：由算法3 知r g r m t o r 方法的迭代矩阵为 h r g r m t o r n k 胍 q 咄蚜1 眠晟+ ( 1 一u 4 ) ， = l ( 1 一“1 ) d + ( u 1 一u 2 ) l + ( u 1 一u 3 ) 巩+ u 1 魄 d 一( u 2 l k + 3 最) 因为户( 以g 冗m t o r ) 墨，( 1 g m f 一r i ) ，所以只需在定理条件下证明p ( | 啻船r m t o r i ) 类似定理2 2 1 的证明 时 i ) 当osu 2 u l ，osu 3 u l ，o u l 1 ，l ，o u 4 2 ( 1 + p u l ) ，p u l = 1 一u l + u l p h r g r m 田o r 两边同乘以抚可得 n 一一 ， ( 慨) 1 帆+ 1 1 一岫i 弧) 甄 k = 1 n 1 1 一叫4 l ，+ u 4 ，一u 1 “趣( 坻) 一1 i d l ( ， = 1 a 茎1 1 一u 4 l j + u 4 d i - 1 i 引) 毋 u 1 岫i d r l i d l j 一( i d r l i b i + e e e t ) 吼 k = 1 o 日只g r m t 。月i z 。 1 1 一“4 i j + 咄，一u l u 4 ( 1 一风) 4 上矗 七= 1 当满足定理条件时就有 故 = 1 u 4 1 i + “且( u 1 1 + u 1 风) 】z 。 由r g r m t o 兄l z e z p ( 1 z k g r m r 。 rj ) 1 i i ) 当1 u 1 2 ( 1 + ，) ，o 茎u 2 茎u 1 ，o 茎岫茎u 1 ，o u 4 2 ( 1 + 风，1 1 ，儿1 u 1 1 + u l p 时 自册兄m t 。r i 壹( 觑) 一觑+ i 咄一1 l 觑】毋 k = 1 l 峨一l l ，+ u 4 1 l d l ( 2 一u 1 ) ，一u 1 】毋 l 岫一1 l + u 4 ，一u 4 ( 2 一1 ) ，一“j l ( j + e e e t ) & 七= l d 。譬 咄 筮二章整体松弛并行多分裂t o r 法及敛散速度的比较 1 5 两边同乘z 。可得 n 1 月_ g 兄m t 。r l 耽i “且一l i z 。+ “山政一u 4 ( 2 一u l u lp e ) 戤j = 1 = j “血一lj + 岫( u i 一1 + 叫i 风) z 。 = i u 4 1 i + u 4 户。1 z 。 当满足定理条件时，就有 故 定理得证 三k g r f r o 只i z f 。e p ( i 西( 擒m t o rj ) 1 口 由于矩阵a 是日阵包含下面推论中的三种情况，则也立即有下面的推论 推论2 2 4让矩阵a 只。满足以下条件之 i ) a 是m 阵 i i ) a 是严格或不可约对角占优阵 i i i ) a 是对称正定l 阵 且a = d 一仇一吼一巩，南= 1 ，2 ，q ，其中饥，最为严格下三角矩阵，巩为严格上三 角矩阵，( 脚= j d f i 反i 一最一i 魄i = j d i i b | 如果 0o 噬忱9 1 ) 0 岫。1 ) 吣 o 均为实数，满足i 目1 i + l 目2 i 1 定理2 1 4 和推论2 1 7 中，只要o u 1 2 ( 1 + 、2 日1 目2 ) ，o u 2 2 ( 1 + 阢。) 时即可收敛，其中儿，= 1 1 一u l l + 吼l ；定理2 2 1 ，推论2 2 3 和推论2 2 4 中， 只要osu 2 曼u 1 ，os 岫su 1 ，o 1 耳了丽，o u 4 去时即可收敛，其中 儿，= j 1 一u l l + 、互辄1 当日1 ：1 2 ，口2 ：1 3 时，定理2 1 4 和推论2 1 7 中，只要o u 1 3 一怕，o 2 ( 1 + m ，) 时即可收敛，其中m 。= 1 1 一u l l + 孚u 1 ；定理2 2 1 推论2 2 3 和推论2 2 4 中，只要o u 2 u 1 ，o 吣墨u 1 ，o u 1 3 一狮，o 咄 番岳时即可收敛，其中 p ：f l u 1 + 乎u 1 2 3 2矩阵实例二 令 a = 100 一 l0 0一1 0o0 000 0 一p 00 00 10 一p1 = d b = 100 010 00 1 000 o oo 00 0 0 00 10 o1 0 00 00 0 p 0 000 0 o0 0v 0o 0o 00 p0 其中p ( i 口l _ 1 l b l ) = v ，一为实数，满足川 l 定理2 1 4 和推论2 1 7 中，只要o u 1 2 ( 1 + ) ，o u 2 2 ( 1 + 阢。) 时即可收 敛，其中儿，= 1 1 一u l l + 川1 ；定理2 2 1 ，推论2 2 3 和推论2 2 4 中，只要o u 2 u 1 ，o u 3 u 1 ，o u 1 南，o u 4 番岳即可收敛，其中儿，= 1 1 一u l i + u 1 当= ；时，定理2 1 4 和推论2 1 7 中，只要o u 1 ；，o u 2 2 ( 1 + m 。) 时即可收敛，其中几，= 1 1 一叫1 l + “，l ；定理2 2 1 ，推论2 2 3 和推论2 2 4 中，只要 o 此u 1 ，osu 3su 1 ，o u l ；，o u 4 百差：- 即可收敛，其中儿。= 1 1 一u l l + j u l 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 1 7 2 4 数值试验 2 4 1数值试验一 考虑如下二维非线性非稳态扩散方程 a 筹= 岛象+ 蒜+ k 筹+ 嚣+ e “+ 9 ，t 。，。z ，”s t 9 瓦3 岛石+ 勺百+ 如瓦+ 丽+ 8 “+ 9 ， 之o ，o z ，sl - 初始条件为“( z ，可，o ) = ，( z ，可) ，边界上取零d 谢c h e l e t 边界，其中 q = c + ( m “3 p ，c z = n l 札m 。户，c ”= 2 “m 。p ， k = c ls i n ( 2 7 r 茁) + 白，b = d ls i n ( 2 7 r 可) + d 2 ， 而c ，n o ，n l ，n 2 ，p ，m z ，m ，c l ，国，d 1 ，d 2 ，e ，9 为常数 我们考虑模型：取岛= n o = m 。= m ”= e = g = 0 0 ，0 1 = 。2 = 1 5 1 2 7 3 3 ，p = 0 7 9 ，c 1 = d l = 1 ，c 2 = 如= 0 0 0 1 区域分解方式依处理机台数而定，如有1 6 台处理机， 则我们可用4 4 方式( 如下图) 子区域由左向右，自下而上编号，每个子区域内按自然顺 序编号，并由m p i 并行程序设计平台将其映到相应处理机上 1 3 1 41 51 6 9 1 01 11 2 56 78 1234 我们用凝固系数法及五点差分格式离散上述方程，所得线性代数方程组是块五对角形 式如网格划分为1 6 + 1 6 的，区域分解为4 * 4 方式，用五点差分格式离散，则所得的线性 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 1 8 代数方程组系数矩阵形式如下 其中主对角块a “是五对角的且其非零元模式与a 之非零块模式相同，其他块为对角的 我们在一台m p p 并行机上进行数值试验，取多分裂是相同的，即螈= m ，权矩阵取 为j 通过大量试验，我们得到：用1 6 台处理机时，整体松弛并行多分裂( l g r m - t o r ) 方法近似最优参数为 u 1 = o 5 ，u 2 = 0 9 ，u 3 = 1 2 ，“血= 1 3 局部并行多分裂( l m s o r ) 方法的近似最优参数为 u 1 = o 8 ，“2 = l 我们比较了l g r m t o r 方法和l m s o r 方法的墙上时间、收敛性和加速比等 当节点是4 0 0 4 0 0 ，误差是e 一1 0 一3 时，l g r m t o r 方法和l m s o r 方法比较 结果在表2 1 中给出，改进性能( ) 是用分式1 一；蠹计算得到的 图形f 培1 ，f 培2 和f 谵3 给出了两种方法在各处理机规模上残差范数下降情况的具 体比较。 u ”埔 毗 乩们h 愁 2 j 2 口 “ “扎 札 机 慧 o o m m m 姗 岫m 如 舢 佃 蛔 f 如切如 ：莹 ：妻埘删 删 凡 如如 如 札轧 如 舢舢山 舢 m 加舢 舢 札赴 如 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 表2 1 ：并行性能比较 处理器l m s o rl g r m t o r性能 台数墙上时间迭代步墙上时间迭代步改进 12 9 3 0 77 42 3 0 8 46 l2 1 - 2 3 27 o 32 2 84 0 8 4 91 3 24 2 2 2 41 9 6 5 82 7 01 ，1 6 7 91 6 84 0 5 9 8 0 9 9 1 2 2 9 8o 6 2 8 12 0 13 6 6 3 1 60 7 1 0 53 1 30 3 7 0 52 1 84 7 9 6 3 20 5 2 1 23 3 40 2 7 3 92 3 54 7 4 6 f 培l ：c o m p a r i s o no fl m s o ra n dl g r m t o r o n1p r o c e 8 s o ra n d2p r o c e s s o r s 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 2 0 r m t o ro n4p r o c e s s o r s 棚1 d8p r o c e s s o r s g3 ：c o m p 盯i s o no fl m s u ra n dl g r m 一上u ro n1 6p r o c e s s o ra n d3 2p r o c e s s o r s 由图形f 蟾1 ，f 培2 和f i g3 易知：( 我们的) l g r m t o r 方法确实比( 文献中的) l m s o r 方法收敛速度快，且随着处理器的增加收敛速度越来越明显 我们也将( 本文) l g r m t o r 方法和( 文献) l m s 0 r 方法的并行加速比进行了比较， 加速比是利用在一台处理器的串行时间比上在p 台处理器上的并行时间得到的为了公 平，我们将两种方法都运行5 0 0 步迭代，问题规模仍为= 4 0 0 4 0 0 ，结果见表2 ，2 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 处理器l m s o rl g r m t o r 台数墙上时间加速比墙上时间加速比 1 2 0 9 8 8 71 1 9 4 2 1 21 2 1 6 6 5 2 1 l - 2 61 6 2 1 6 71 2 0 44 ，3 4 3 64 8 33 7 5 7 05 1 7 8l | 8 1 3 01 1 5 81 7 4 2 3l l - 1 5 1 61 0 6 7 31 9 6 7o 9 2 9 72 0 8 9 3 20 5 5 2 03 8 0 20 5 8 2 33 3 3 5 表2 3 ：并行加速比比较，= 8 0 0 8 0 0 处理器l m s o rl g r m t o r 台数墙上时间加速比墙上时间加速比 1 8 6 2 3 2 9 18 5 3 5 7 21 27 5 6 6 7 51 1 47 3 8 0 8 71 1 6 43 9 2 4 6 02 2 03 7 3 9 8 82 2 8 81 8 5 8 9 54 6 41 7 2 5 6 74 9 5 1 6 4 7 8 6 31 8 0 24 3 2 0 11 9 7 6 3 22 ，2 7 7 23 7 8 72 0 8 4 93 7 4 8 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 2 2 由表2 2 易知，当分别用4 ，8 ，1 6 ，3 2 台处理机时，均出现了超线性加速，这说 明随着处理机台数的增加，各处理机分担的未知量减少，从而c a c h e 命中率会增加，计算 时间相应减少，表2 3 用1 6 ，3 2 台处理机时也出现了超线陛加速 当问题规模是= 8 0 0 8 0 0 时，进行5 0 0 次迭代，我们同样比较了( 我们的) l g r m t o r 方法和( 文献中的) l m s o r 方法的并行加速比，结果见表2 3 以上试验表明：我们的方法确实对文献方法进行了有效的改进，最高可达4 7 9 6 ，且 处理机台数越多，改进越来越显著方法良好的并行加速比表明，我们的方法具有好的并 行可扩展性 2 4 2数值试验二 我们举一个微分方程差分离散后的线性方程组求解的实例，以比较松弛型并行多分裂 s o r 方法，l g r _ t o r 和l g r _ s o r 方法，验证我们方法的有效性，为方便起见取n 一6 a = 4 10 221 5 0l3 001 5 000 00o 0o 0 o0o 一100 220 14 1 o22 6 = 3 5 5 3 5 5 4 4 e l = d i 0 9 ( 1 ，1 ，o ，o ，o ，o ) ，e j = d t 。9 ( o ，0 ，1 ，1 ，o ，o ) ，。既= d i o g ( o ，o ，0 ，o ，1 ，1 ) l 1 = 0 0o 1oo 010 o oo 3 o o0 0o0 ooo o0o o00 0o0 1 0o o o 80 00ooo0 1 5oo0oo 00 50000 0o0 700o 0oo0 500 oo00o 40 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 2 3 三3 = l l = 上+ 最 l 2 = l + 毋= 3 = 玟+ 巩 01 50oo0 0o一1 20oo 0 o 0o 3 o o 0o000 80 00o0o0 0 3o00o0 0o 70000 000 100o 0000 9o0 00000 50 0 7ooooo 0o 3o0o0 o0o 2000 o 20000o 00 80o00 000 5000 00o00 5o 仉= d l k 一4 ，= 1 ，2 ，3 + + + 0o0000 0 700000 0o 30000 000 2o00 00o0 1oo 00oo 一0 ，3 0 ooo0o 0 0 8o0oo0 0o 2000o oo0 5oo0 oo0o 10o 00o00 2o o 4oooo0 00 7o000 00 一o 7 000 000o 100 o00o0 40 先取初始值z ( o ) = ( 1 0 ，3 0 ，一2 0 ，一4 0 一8 ，9 ) 7 ，误差精度为e = 1 0 ”，经实验知，我们 的方法和文献 3 、6 、1 1 中的方法进行了比较，我们的方法较系统松弛法改进性能如 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 2 4 下表所示。 方法近似最优参数选取迭代步数性能改进文献 s y s t e mr e l a x e du 1 = 1 ，2 = o 9 4 7 00 3 】 l g r m s o r l = 0 6 2 ，u 2 = 1 5 2 5 91 5 7 1 本文 l g r m t o r o l = o 6 6 ，u 2 = 0 0 1 ，u 3 = o 0 0 ，咄= 1 5 1 4 93 0 0 0 本文 此时，我们的方法较局部松弛s o r 法改进性能如下表所示 方法近似最优参数选取迭代步数性能改进文献 l m s o r u 1 = 1 ，u 2 = 0 9 4 6 7 0 6 】 l g r m 。s o r u 1 = 0 6 2 ，u 2 = 1 5 2 5 91 1 9 4 本文 l g r m t o r u 1 = 0 6 6 ，= 0 0 1 ，。3 = 0 0 0 ，岫= 1 5 1 4 92 6 8 7 本文 再取初始值z ( o ) = ( o ，1 0 ，一2 0 ，2 0 ，3 0 ，一3 0 ) t ，误差精度仍为e = 1 0 1 0 ，我们的方法较系统 松弛法改进性能如下表所示。 方法近似最优参数选取迭代步数性能改进文献 s y 8 t e mr e l a x e du 1 = 1 ，2 = 0 9 4 6 90 3 l g r m s o r u l = 0 6 2 ，u 2 = 1 5 2 6 0 1 3 0 4 本文 l g r m - t o r u l = o 6 6 ，u 2 = 0 0 1 ，u 3 = o 0 0 ，“且= 1 5 1 5 02 7 5 4 本文 此时，我们的方法较局部松弛s o r 法改进性能如下表所示。 方法近似最优参数选取迭代步数性能改进文献 l m s o r 1 = 1 ，u 2 = 0 9 4 6 7 0 6 】 l g r m s o r u 1 = 0 6 2 ，叫2 = 1 5 2 6 01 0 1 4 本文 l g r m t o r“1 = 0 6 6 ，u 2 = 0 o l ，u 3 = 0 0 0 ，“且= 1 5 15 02 5 3 7 本文 我们的方法和文献 3 、6 、1 1 中的方法误差曲线比较分别如下图所示 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 2 5 由上面几个试验得到：我们的方法较文献中的方法误差曲线下降快，两个松弛参数的 l g r m s o r 法比局部松弛s o r 法较优，收敛速度提高近1 6 ；四个松弛参数的l g r m 一 山o三g磊苎。要弩哥 jo三pn暑。苎。呈j哥 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 2 6 t o r 法比以往任何松弛型多分裂都较优，收敛速度较局部松弛s o r 法提高近3 0 由 此可见，我们的方法确实对文献中的方法进行了有效的改进 2 5 敛敖速度的比较 基于矩阵a 的多分裂而提出的求解大型线性代数方程组a z = 6 ( z 加r “) 的并行 矩阵多分裂t o r 迭代算法以及相应于其松弛参数的特殊选取而产生的并行矩阵多分裂 j a c o b i ，g s ，j o r ，s o r ，a o r 迭代算法，不仅具有广泛的实用性质，而且具有很高的理论 研究价值因而，吸引着许多作者致力于这类算法的研究本节，在文献 1 9 】的基础上， 我们通过进一步细致地讨论上述算法迭代矩阵的谱半径之间的相互关系，比较了它们的收 敛速度和发散速度 为方便起见，在以下的讨论中我们不防约定施叼( a ) = ，我们熟知，矩阵多分裂t o r 迭代矩阵为 a h t o r = 芝二e k 【j 一( u 2 k + u 3 良) 一1 【( 1 一u 1 ) f + ( u l u 2 ) k + ( u 1 一u 3 ) 良+ u 1 巩 选用不同的u ，u 。，u s ，我们将得到下面不同的并行多分裂迭代格式 u 2 = 峨，则得到矩阵多分裂a o r 迭代矩阵 矾d r = 甄 j 一“2 l _ 1 【( 1 一u 1 ) j + ( u 一u 2 ) 以+ u ，巩】， = l 其中k = 反+ 凡 u = u 。= u s ，则得到矩阵多分裂s o r 迭代矩阵 u 1 l ) 一1 ( ，一u 1 ) ，+ u 1 巩】 u 1 = u 2 = 峨= 1 ，则得到矩阵多分裂g s 迭代矩阵 厶) - 1 巩 u 2 = u 3 = 0 ，则得到矩阵多分裂外插j a c o b i ( j o r ) 迭代矩阵 日j o r = ( 1 一u 1 ) ，+ u 1 b u玩 。m = ros 日 ，巩 。脚 1 1 占 一 gh 第二章整体松弛并行多分裂t o r 法及敛散速度的比较 2 9 i ) o 峨，岫u l 曼1 1 o ) ，且月t o 冗收敛 i i ) 0 u 2 茎u 1 1 ( u 1 o ) ，且日a o r 收敛 i i i ) o u 1 1 ，上b o r ，且日s d r 收敛 i v ) 0 9 ( ”，+ ( 1 一u ) j o g ( m ， ) 一1 = u 岛 f d 一( q 反+ 风最) 】_ 1 七= i= 1 ( 1 一佻) d + ( 讯一n ) 反十( 佻一脓) 最+ 傀氓n ) 一( o k l k + 臃最) 】一1 7 k 笪三童墼签坠塾韭塞堂垒坌翌! q 垒鲨壁篁墼遭壅盟些堑j 6 证明：与前面的定理证明类似：只需证明1 日( ) ( d 女，觑，饥) 1z 曼阮( m = o ，1 ，o p 1 ) 即可 i ) 若o a k 墨1 k ，o 茎风1 k ，o ，y k 1 时 1 日( m ) ( d ，凤，饥) j 瓢s 取( 1 一协+ 协p ( 乓) ) 9 ”姊茁e = l 晚( 1 一讥+ 讥p ( 五) ) 噩 这里以2 燃( 1 讯+ 讥p ( 五) ) i i ) 若os 口ks 讯 os 凤讥，1 讥 2 ( 1 + p ) 时 日( m ) ( n ，凤，仇) l 文量邑( 讥一1 + 讯p ( 以) ) 。( m ，砷致 七= l 既m 一1 十协p ( 以) ) 妖 南= 1 = 目。甄， 这里口e 2 品忿( 讥一1 + 讥p ( 以) ) 定理得证 口 关于整体松弛非定常多分裂多参数t o r 法我们也有下面的收敛性定理 定理3 1 3设a 是矩阵，对七= l ，1 ，d ，r 为下三角