（流体力学专业论文）块三对角方程组的可扩展并行算法及其应用研究.pdf

上海大学博士学位论文 摘要 偏微分方程的数值求解是科学与工程计算的重要任务，块三对角线性方程 组是偏微分方程离散格式的主要形式之一。本文系统地研究了块三对角线性方 程组直接求解方法的可扩展并行算法及其应用，主要工作如下： 1 将三对角线性方程组的r c d ( r e c u r s i v e d o u b l i n g ) 方法，推广n - f 块三 对角线性方程组，得到b r c d ( b l o c kr e c u r s i v ed o u b l i n g ) 方法。该方法将块l u 分解的时序性较强的计算转化成矩阵的乘积计算，有利于设计并行算法；同时 给出了块l u 分解方法、b r c d 方法和s b p ( s e q u e n t i a lb l o c kp r e f i x ) 方法的反 向与双向计算公式，在计算中使用不同方向的计算公式可以减少计算量；给出 了一个数值稳定的块三对角线性方程组快速b o e r ( b l o c ko d d e v e nr e d u c t i o n ) 求解公式，提高了计算精度和速度； 2 对于l a r r i b a 等提出的三对角线性方程组的重叠分割并行方法，一方面 将它推广到了块三对角线性方程组，该方法对于强块对角占优块三对角线性方 程组的求解有较高的并行效率；另方面将它与非重叠分割并行方法的缩减方 程组结合，提出了块三对角线性方程组的有通信重叠分割并行方法，对于弱块 对角占优的块三对角线性方程组，该方法可以用少量通信代替过量的计算，保 证了精度和计算效率； 3 对严格块对角占优块三对角线性方程组的两类缩减方程组，提出了近似 求解方法和相应的并行算法，该方法的通信次数是可调整的，可以通过它的调 整来控制精度； 4 对严格块对角占优的块三对角线性方程组提出了多个可扩展的重叠与非 重叠分割并行算法( 统称p b d d a 算法) ，其中基于块u j 分解的算法统称 p b d d a l u 算法、基于b o e r 的算法统称p b d d a o e 算法。给出了两种通信 模式，其特点是：仅使用局部通信；通信复杂度可调整；每次通信都是具有一 定间隔的相邻处理器之间的单向数据传递。给出了相对误差与三个可调整的指 标1 , 0 ( 通信复杂度指标) 、q + g ( 子问题规模指标) 和p ( 处理器数量即算法 并行度指标) 的关系。p b d d a l u 算法是对p d d 方法的推广，在推广中使用 v 上海大学博士学位论文 了反向块l u 分解，改进了回代方法，比直接使用p d d 方法求解块三对角线性 方程组减少了将近3 0 的计算量； 5 提出了一类t o p e l i t z 块三对角线性方程组的p b d d a - o e 算法公式；使 用这个公式进行高维p o i s s o n 方程第一边值问题的数值求解：研究了p b d d a o e 算法的性能，提出了保证精度和并行效率的分治策略； 6 利用以上t o p e l i t z 块三对角线性方程组的p b d d a o e 算法公式进行高 维抛物型方程初始边值问题的数值求解，研究了p b d d a - o e 算法的性能，提出 了保证精度和并行效率的分治策略； 7 提出了另一类t o p e l i t z 块三对角线性方程组的p b d d a o e 算法公式； 使用这个公式进行高维双曲型方程初始边值问题的数值求解；给出了控制精度 与并行效率的分治策略。 关键词：可扩展并行算法，并行性能评价，块三对角线性方程组，严格块 对角占优，高维p o i s s o n 方程，高维抛物型方程，高维双曲型 方程。 v i 上海大学博士学位论文 a b s t r a c t n u m e r i c a ls o l u t i o no f t h ep a r t i a ld i f f e r e n t i a le q u a t i o n s ( p d e s ) i sav i t a lt a s ko f s c i e n t i f i ca n de n g i n e e r i n gc o m p u t i n g t h eb l o c kt r i d i a g o n a ls y s t e m sa r ea l w a y st h e p r i m a r y f o r mo ft h ed i s c r e t es c h e m e so fp d e s t h i sp h d d i s s e r t a t i o n s y s t e m a t i c a l l ys t u d i e st h es c a l a b l ep a r a l l e la l g o r i t h m sa n da p p l i c a t i o n sf o rs o l v i n g d i r e c t l yt h eb l o c kt r i d i a g o n a ls y s t e m s m a i na c h i e v e m e n t sa r el i s t e db e l o w ： 1 t h er e c u r s i v ed o u b l i n g ( r c d lm e t h o df o rs o l v i n gt r i d i a g o n a ls y s t e m si s e x t e n d e dt ot h eb l o c kt r i d i a g o n a ls y s t e m sa n db l o c kr e c u r s i v ed o u b l i n g ( b r c d ) m e t h o di sd e v e l o p e d t h eb r c dm e t h o dt r a n s m i t st h es e q u e n t i a lc o m p u t i n go f b l o c kl ud e c o m p o s i t i o no f t h em a t r i xi n t ot h ec a l c u l a t i o no f t h em a t r i x e sp r o d u c ti n o r d e rt od e s i g nt h ep a r a l l e la l g o r i t h m s n 伦r e v e r s ea n dt w o w a yc o m p u t a t i o n a l f o r i l l u l a so ft h eb l o c kl ud e c o m p o s i t i o nm e t h o db r c dm e t h o da n ds e q u e n t i a l b l o c kp r e f i x ( s b p ) m e t h o da r ea l s od e s i g n e d t h ec o m p u t a t i o n a lt i m ec a nb e d e c r e a s e dw h e nt h ec o m p u t a t i o n a lf o r m u l a so fd i f f e r e n td i r e c t i o na r eu s e d t h e s t a b l ea n df a s tf o r m u l a so ft h eo d d e v e nr e d u c t i o n ( o e r lf o rr e d u c i n gt h eb l o c k t r i d i a g o n a ls y s t e m sa r ep r o p o s e df o rt h ep u r p o s eo fi m p r o v i n gt h ec o m p u t a t i o n a l a c c u r a c ya n ds p e e d 2 o nt h eo n eh a n d ，t h ep a r a l l e lo v e r l a p p i n gp a r t i t i o n ( p o p ) a l g o r i t h mo f s o l v i n g t r i d i a g o n a ls y s t e m sm e n t i o n e db y l a r r i b ai sg e n e r a l i z e df o rs o l v i n gb l o c kt r i d i a g o n a l s y s t e m s t h ec o m p u t a t i o n a le f f i c i e n c yc a i lb ei m p r o v e dg r e a t l yw h e nt h es t r o n g b l o e l ( d i a g o n a ld o m i n a n tb l o c k 仃i d i a g o n a ls y s t e m sa r ec o n s i d e r e d o nt h eo t h e l h a n d , t h ep o pa l g o f i t h m sw i t hc o m m u n i c a t i o n sf o rs o l v i n gt h eb l o e kt r i d i a g o n a l s y s t e m sa g ed e s i g n e dw h e nt h ep o pm e t h o di sc o m b i n c dw i t hr e d u c e ds y s t e m so f t h en o n - o v e r l a p p i n gp a r t i t i o np a r a l l e la l g o r i t h m s v c h e nt h ew e a k l yb l o c kd i a g o n a l d o m i n a n tb l o c kt r i d i a g o n a ls y s t e m sa r ec o n s i d e r e d ，t h em e t h o dc a nb eu s e dt o r e p l a c et h ee x c e s s i v ec a l c u l a t i o nw i t hs m a l lc o m m u n i c a t i o n st o e n s u g et h e c o m p u t a t i o n a le f f i c i e n c ya n da c c u r a c y 3 t h ea p p r o x i m a t em e t h o da n di t s r e l a t e dp a r a l l e la l g o r i t h m sf o rs o l v i n gt w o r e d u c e ds y s t e m so ft h es t r i c t l yb l o c kd i a g o n a ld o m i n a n tb l o c kt r i d i a g o n a ls y s t e m s a r ep r e s e n t e d t h ec o m m u n i c a t i o nt i m e so ft h i sm e t h o di sa d j u s t a b l e ，w h i c hc a nb e u s e dt oc o n t r o lt h ec o m p u t a t i o n a la c c u r a c y 4 s e v e r a ls c a l a b l ep a r a l l e la l g o r i t h m s ( r e f e r r e dt oa sp b d d aa l g o r i t h m s ) w i t h o v e r l a p p i n go rn o n - o v e r l a p p i n gp a r t i t i o nf o rs o l v i n g t h es t r i c t l yb l o c kd i a g o n a l d o m i n a n tb l o c kt r i d i a g o n a ls y s t e m sa r ed e v e l o p e d t h ea l g o r i t h m s b a s o do nb l o c k l ud e c o m p o s i t i o nm e t h o d a l en a m e dp b d d a ，l ua l g o r i t h m s t h eo t h e r s ，b a s e do n b o e rm e t h o d a r ee a l l e dp b d d a o ea l g o r i t h m s t w oc o m m u n i c a t i o np a t t e r n s w i t ht h ep r o p e r t i e so fl o c a lc o m m u n i c a t i o n ，a d j u s t a b l ec o m m u n i c a t i o nc o m p l e x i t y v i i e 海大学博士学位论文 a n do n e - s i d e dm e s s a g ep a s s i n gb e t w e e nt h en e i g h b o r i n gp r o c e s s o r sa tc e r t a i n i n t e r v a li ne a c hc o m m u n i c a t i o na r eg i v e n t h er e l a t i o n sb e t w e e nt h er e l a t i v ee n - o r a n dt h r e ea d j u s t a b l ei n d e x e s ，i e ，( t h ec o m m u n i c a t i o nc o m p l e x i t yi n d e x ) ， q + 虿( t h es u b s y s t e m s s c a l ei n d e x ) a n d p ( t h en u m b e ro fp r o c e s s o r s o rt h e a l g o r i t h m sp a r a l l dd e g r e ei n d e x 、a r ed i s c u s s e d t h ep b d d a l ua l g o r i t h m sa l e c o n s i d e r e da st h ee x t e n s i o no fp d dm e t h o di nt h es e n s eo fu s i n gt h eg e v g r s eb l o c k l ud e c o m p o s i t i o nm e t h o da n di m p r o v i n gb a c k s u b s t i t u t i o nm e t h o dt od e c r e a s et h e c o m p u t a t i o n a lc o m p l e x i t yu p t o3 0 ，c o m p a r e dw i t hd i r e c tp d dm e t h o d 5 t h ep b d d a o ea l g o r i t h m so fat o p e l i t zb l o c kt r i d i a g o n a ls y s t e m sa r e o b t a i n e da n du s e dt os o l v et h ef i r s t b o u n d a r y v a l u ep r o b l e m so ft h e m u l t i d i m e n s i o n a lp o i s s o ne q u a t i o n s t h ep e r f o r m a n c ee v a l u a t i o na n ds c a l a b i l i t yo f t h ep b d d a o ea l g o r i t h m sa r ed i s c u s s e d t h ed i v i d e d a n d - c o n q u e rs t r a t e g yt o e n s u r et h ee f f i c i e n c ya n da c c u r a c ya r ed e v e l o p e d 6 t h ep b d d a o ea l g o r i t h m so ft h et o p e l i t zb l o c kt r i d i a g o n a ls y s t e m sa r e u s e dt os o l v et h ei n i t i a lb o u n d a r yv a l u ep r o b l e m so fm u l t i d i m e n s i o n a lp a r a b o l i c e q u a t i o n t h ec a p a b i l i t ya n ds c a l a b i l i t yo f t h ep b d d a - o ea l g o r i t h m sa r ed i s c u s s e d t h ed i v i d e d - a n d - - c o n q u e rs t r a t e g yt og u a r a n t e et h ee f f i c i e n c ya n da c c u r a c ya r e o b t a i n e d 7 n e wf o r m u l a so fp b b d a o ea l g o r i t h m so fa n o t h e rt o p e l i t zb l o c k t r i d i a g o n a ls y s t e m sa r eu s e dt o s o l v et h ei n i t i a lb o u n d a r yv a l u ep r o b l e m so f m u l t i d i m e n s i o n a l h y p e r b o l i ce q u a t i o n s t h ed i v i d e d a n d c o n q u e rs t r a t e g y o f c o n t r o l l i n ge f f i c i e n c ya n da c c u r a c ya r ep u tf o r w a r da sw e l l k e y w o r d s ：s c a l a b l ep a r a l l e la l g o r i t h m s ，p a r a l l e lp e r f o r m a n c ee v a l u a t i o n , b l o c k t r i d i a g o n a ls y s t e m s ，s t r i c t l y b l o c k d i a g o n a l d o m i n a n t ， m u l t i - d i m e n s i o n a lp o i s s o ne q u a t i o n s ，m u l t i d i m e n s i o n a l p a r a b o l i c e q u a t i o n s ，m u l t i - d i m e n s i o n a lh y p e r b o l i ce q u a t i o n s v 1 1 1 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：虺丝)e t 期：兰望：! ：? 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：7 翌：f 垒导师签名：逮丛：日期：羔生壑：3 王! n 第一章绪论 1 1 本文研究的目的和意义 随着社会和科学的发展，人们研究问题的深度和研究领域不断发展，对计 算机的性能不断提出更高的要求。并行计算机技术的不断发展，为满足这些要 求提供了基本的硬件条件。当前，分布式存储并行处理机系统已经广泛应用于 包括计算力学在内的各类科学和工程计算问题。然而，软件研究与应用的滞后 制约了这类计算机系统性能的发挥。软件的核心是算法，加强适合分布式并行 计算环境的算法研究是十分必要的。 偏微分方程是科学计算和工程问题中的主要模型方程。流体力学问题的控 制方程一般是椭圆型方程、抛物型方程、双曲型方程或者是混合型方程，因此， 数值求解椭圆型方程、抛物型方程和双曲型方程这三种类型的方程，无论是算 法设计还是实际应用，都是计算流体动力学的主要任务和重要的研究领域。数 值求解的基本思想是将偏微分方程进行离散化处理，常用的离散方法有有限差 分方法、有限元方法、小波方法等，使用这些离散方法得到偏微分方程的离散 格式，该离散格式的解就是偏微分方程的离散解或者数值解。椭圆型方程、抛 物型方程和双曲型方程等的差分格式都是块三对角线性方程组，因此大规模块 三对角线性方程组的求解方法是偏微分方程数值算法研究首先遇到的最重要的 课题之一。 长期以来，伴随着计算环境的不断变化，人们也在不断探求能适应新计算 环境的块三对角线性方程组求解方法。并行算法就是在并行计算环境中产生和 发展的。所谓并行计算，就是将一个需要求解的问题，分解成若干子问题，并 将这些子问题分配到并行计算机的若干处理器上，由这些处理器按照并行算法 共同协调求解这些子问题，从而完成对初始问题的求解。目前，在分布式计算 环境下，大规模块三对角线性方程组求解的高效率可扩展并行计算方法的研究 与应用具有非常重要的理论和实际意义，已经成为科学计算的重要问题之一。 分布式计算环境中的大规模块三对角方程组并行求解问题，仍然缺少高效 率的可扩展并行计算方法，全局通信问题是面临的主要瓶颈之一。全局通信问 题对于共享存储并行环境的影响不大，但是在分布式并行机上全局通信对计算 效率的影响较大。全局通信体现了整个问题的全局综合，虽然这种全局性是问 题本身固有的、无法避免的，但全局通信并非不可避免。迭代法和直接法是求 解块三对角线性方程组的两个基本方法。迭代法是极限方法，只能得到理论上 的近似解，并且迭代法所必须的预条件子选取是个困难的问题。直接法建立在 矩阵分解、矩阵求逆等数学理论基础上，理论上可以得到精确解。但是在分布 式并行计算环境下，直接法的并行计算可能会遇到全局通信和计算量过大的问 题。有学者认为直接法需要解决全局通信所产生的瓶颈问题，通信开支较大， 而迭代法只需要局部通信，所以更适合分布式计掣”。事实上，对于规则的大 规模块三对角线性方程组，直接法比迭代法要快得多，对于块对角占优的块三 对角线性方程组，通过充分挖掘其内部的并行性，使用直接法同样可以用局部 通信完成计算。而迭代法的每一次迭代都需要启动通信，所以其通信启动次数 和通信量都与迭代次数成正比，在共享存储并行计算机上，这一问题尚不突出， 而在分布式计算机上，大量通信启动会降低计算效率，失去并行计算的意义。 所以，加强大规模块三对角方程组直接求解的计算方法特别是适合分布式计算 环境的可扩展并行计算方法的研究是非常必要的。 本文研究块三对角线性方程组直接解法的可扩展并行算法，意图通过挖掘 偏微分方程及其有限差分格式的内在并行性，减少计算量，避免全局通信，提 出适合分布式并行计算环境的、能求解偏微分方程问题的大规模块三对角线性 方程组的求解算法。 本课题来源于教育部科学技术研究重点项目“自适应并行算法及其应用” ( 编号：2 0 5 0 5 1 ) 。 1 2 块三对角线性方程组并行算法的研究概况 目前，块三对角线性方程组直接求解的并行算法并不多，块三对角线性方 程组的并行算法多是从三对角线性方程组的并行算法推广而来，并且可以用于 三对角线性方程组，高维偏微分方程化成一维问题后其差分格式就转化成三对 角线性方程组，因此对求解三对角线性方程组的并行算法进行法研究是十分必 2 要的。三对角线性方程组直接求解的基本计算方法主要有四类：传统的矩阵分 解法( l u 分解、q r 分解、c h o l e s k y 分解等) 、h o c k e y 的奇偶约化( o d d - e v e n r e d u c t i o n ，简称o e r ) 方法【2 1 、s t o n e 的递推耦合( r e o u s i v ed o u b l i n g ，简称 r c d ) 方法3 1 和e g e c i o g l u 的p p ( p a r a l l e lp r e f i x ) 方法【4 】。此外还有其他计算方 法，比如d e k k e r 等的最小模方法【5 一，c o l e 的s k e l e t o n s 方法1 7 。 矩阵的分解有许多方法，经常用于三对角线性方程组直接求解的有l u 分 解、q r 分解、c h o l e s k y 分解等，主要形式是乘分解( 因子分解) 与和分解。 c a o 等讨论了用c h o l e s k y 分解法求解正定对称的块三对角线性方程组【8 】。 矩阵分解法有许多具体的形式，以u j 分解为例，大致有两个方向相反的 分解法和双向分解法，每个分解法又有许多具体的计算公式，这些分解法的重 新组合又产生新的分解法。在设计并行算法时，针对具体的问题和计算环境， 人们还在不断组合出新的矩阵分解方法，比如c h a w l a 等2 0 0 3 提出的w z 分解 法【9 1 。 o e r 方法是h o c k e y 在1 9 6 5 年研究p o i s s o n 方程的数值求解时提出的2 1 ， 被用来求解三对角线性方程组，可以用于弱对角占优的三对角线性方程组。一 般情况下，该方法的计算量比较大，但是该方法可以使各方程的约化同时进行， 具有一定的并行性，容易实现并行计算。该方法有消奇和消偶两个基本形式， 可以混合使用，构造各种各样的算法。一些文献中提出的奇偶消元法，理论上 是o e r 方法的等价形式，但是计算量不同。 r c d 方法是s t o n e 于1 9 7 3 年提出的，是l u 分解法的变型，它将l u 分解 法公式写成矩阵连乘积的形式，从而将l u 分解法时序性较强的计算变成了递 推倍增计算，发掘出隐含在串行计算过程中的并行性，实现了并行计算f 3 1 。该 方法也有两个方向相反的计算公式和双向计算公式，可以混合使用，构造各种 算法。 p p 方法是e g e c i o g l u 于1 9 8 8 年提出的，它利用非对角线元素进行消元，可 以用于非对角占优的三对角线性方程组，它将消元过程及回代过程写成矩阵连 乘积的形式，发掘出隐含在串行消元计算过程中的并行性，实现了并行计算【3 】。 该方法也可以设计两个方向相反的计算公式和双向计算公式，混合使用，可以 构造各种算法。事实上，h u a n g 等已经提出了双向p p 方法【1 0 】。 随着分布存储计算机计算环境的应用与发展，人们又在研究适合分布存储 计算环境的并行算法。分治方法就是在这样的背景下产生和发展的，它的主要 思想是充分利用问题的内在并行性，将大问题分割成小问题，分别由各个处理 器完成计算。分治方法被不断改进，正在形成一些规范和标准，逐渐成为分布 存储计算环境中并行计算的基本技术。w a n g 于1 9 8 1 年提出的分割法( 又称分 裂法) 是最早基于分治思想的方法，能适用于分布存储计算环境，不仅通信结 构简单，容易扩展至一般块三对角线性方程组的并行求解，而且为相继出现的 许多其它并行算法提供了可行的局部分解策略，因此受到普遍重视【1 1 1 。目前， 分治思想已经成为分布存储计算环境下设计线性方程组并行求解算法的指导思 想和基本技术，近2 0 年来出现的并行算法都是基于分治策略。c h a w l a 等2 0 0 3 提出的w z 分解法，使用w a n g 的分割法进行任务分割，再使用矩阵的w z 分 解进行子方程组的约化【9 】。a m o d i o 、b a n d e l i 和c h u n g 等的并行算法也都是基于 分治思想的 1 2 - 1 4 】。d e k k e r 等基于分治策略提出了最小模方法的并行算法【5 ，6 1 。 b i s c h o f 等提出了s k e l e t o n s 方法的并行算法【15 1 。b a n d e l i 基于分治思想提出的算 法可以与多种其他算法结合，适合多种分布式并行环境和多种任务粒度，可扩 展性好【1 3 】。t s a o 基于分治思想提出了使用l u 分解法的精确算法【1 6 】。b a d i a 等 提出了分布式存储并行机上的一个并行算法，用o e r 方法进行方程组的约化与 回代，用g a u s s 消元法求解缩减方型1 7 1 。a m o d i o 等提出将基于矩阵因子分解法 的三对角线性方程组并行求解算法标准化【l8 1 。s p a l e t t a 等和c l i m e n t 等基于秩1 更新策略和重复分割方法，结合r c d 方法分别提出了三对角线性方程组求解的 两个并行算法1 1 9 , 2 0 。a m o d i o 基于分治思想提出一类优化的o e r 方法的并行算 法，求解缩减方程时使用处理器之间的同步通信，适合中粒度的并行计掣2 ”。 a m o d i o 等针对超立方结构的分布式存储并行计算机系统，基于分治思想提 出了一类o e r 方法的并行算法，使用相邻处理器之间的局部通信，同步( 通 信) 的次数与l o 叠p 成比例，具有良好的可扩展性【1 2 】。a m o d i o 等提出了一类 q r 分解方法的并行算法【2 2 】。m a t t o r 研究了矩阵分解法并行算法的通信机制， 提出了通信复杂度为l o g p 的并行算法【2 3 1 。q i n 等在大规模并行机上，基于矩阵 l u 分解和分治思想，提出了一类使用全局通信的并行算法 2 4 1 。h u a n g 等提出了 4 基于双向p p 方法的大规模同步并行算法【1 0 l 。c l i m e n t 等对于大规模三对角线性 代数方程组，提出了两个基于分治策略的递归并行算法，讨论并实验了处理器 之间的多对多和多对一的两个全局通信模式【2 5 1 。v e r k a i k 将循环消元与循环约化 相结合，提出了a c e rf a l t e r n a t i n gc y c l i ce l i m i n a t i o na n dr e d u c t i o n ) 方法【2 6 1 。 分布存储计算环境中，处理器之间通信是实现并行所必需的，但是它会降 低计算效率，所以应该尽可能减少通信。w a n g 的分割法是基于l u 分解方法的 并行算法，它的逶信开销是随着处理器的增加而增长的【l l 】。经过很多研究者的 努力，已经有了不少的改进型，通信复杂度降为o ( 1 0 9 2p ) ( p 是处理器数量) ， 但可扩展性仍然受到限制。s u n 于1 9 8 9 年对强对角占优的三对角方程组提出了 p d d 算法，通过缩减方程组的近似求解，在机器精度内得到与精确解等价的近 似解，同时将通信复杂度降为常数，大大改善了分割法的可扩展性【2 们。p d d 方 法经过不断改进，已经成为分治策略中近似求解的基本方法【2 ”。p i s k o u l i j s l d 对于严格对角占优的t o e p l i t z 三对角线性方程组提出了一个近似求解的并行算 法，并进行了误差分析【3 2 1 。l a r r i b a 对于严格对角占优三对角线性方程组提出了 在向量并行机上的重叠分割并行近似算法，并将该方法推广到了带状线性方程 组，这个方法利用对角占优的条件，不需要通讯，就可以在机器精度内得到与 精确解等价的近似斛3 3 1 。c l i m e n t 等对于严格对角占优三对角线性方程组提出了 在大规模同步并行机上的重叠分割双向l u 分解方法1 3 4 1 。 许多算法需要挖掘问题内在的并行性，形成规则的通信模式和数据结构， 因此在算法研究中，针对具体计算环境，对已有算法的性能研究和完善也是重 要的方面。 m i c h i e l s e 等对w a n g 的分割法进行了研究，改进了通信，增加了计算与通 信的重叠程度，提高了计算效掣1 1 3 5 1 。s a n t o s 研究了奇偶循环约化法的优化设 计【3 6 l 。y a l a m o v 等讨论了分割法的稳定性【期。s u m i y o s h i 等针对具体的计算环 境讨论b o e r ( b l o c ko d d e v e nr e d u c t i o n ) 方法的性能和程序设计【3 8 1 。s a n t o s 等研究了b o e r 法的优化设计【3 9 l 。l a m b i o t t e 等在向量机上比较了o e r 方法、 r c d 方法和j a c o b i 迭代法的性能，说明了对于大规模计算直接法优于迭代法 4 0 】。 s t o n e 比较了o e r 方法、r c d 方法和b u n e m a n 的方法在多种情况下的性能特 点【4 ”。m e i e r 比较了o e r 方法、l u 分解法与g a u s s 消元法的算法性能特点， 5 并给出了稳定性判据 4 2 1 。w a n g 研究了分割法在多处理机上的性能4 3 1 。z h a n g 讨论了p d d 方法的精度 4 4 1 。b i s c h o f 等针对m p i 编程环境提出了s k e l e t o n s 方 法并行算法的最优化成本设计【1 5 】。l i n 等对于一般的三对角线性方程组提出了 并行算法的最优化成本设计思想c 4 5 1 。c o x 等在以向量机为节点的分布式存储并 行机上，提出了一个并行算法，给出了一个确定多余计算和通信的参数，保持 了负载平衡，并提出了o e r 算法标准化的一种简单描述【4 ”。b r u g n a n o 提出了 一个适用消息传递技术的并行算法【4 7 1 。w a n g 在超立方大规模并行计算机上基 于分治思想讨论了用连续递归法求解三对角线性方程组的并行算法c 4 8 1 。een d eg r o e n 提出了一个o e r 方法的并行算法，针对具体的并行环境设计了通信模 式【4 9 】。s a g h i 等研究了o e r 方法的并行算法在三种并行机上的性能 5 0 。对于三 对角线性方程组的三个求解方法：r c d 方法、o e r 方法和s c d 方法，l 6 p e z 等研究了它们的分治策略，通信模式与复杂度，数据结构与计算复杂度，提出 了它们分治策略的一致结构 5 1 】。n a r a s i m h a n 等在分布式共享存储计算机上，使 用不同的通信方法，比较了三对角线性方程组双向l u 分解方法的并行算法与 p o i s s o n 方程迭代求解的并行算法的性能【5 ”。l 6 p e z 等讨论了基于分治策略的三 对角线性方程组求解算法的正规化和并行化，提出了三对角线性方程组求解并 行算法分治策略的一致结构【5 3 1 。m i i l l e r 等提出了一种将三对角方程组串行算法 并行化的一般方法【州。a b b a s 研究了w a n g 的并行算法在分布式存储计算环境 中运行方案的设计【5 5 】。 块三对角线性方程组直接求解的并行算法很多是由三对角线性方程组的并 行算法推广而来。r o d r i g u e 等将o e r 方法推广到了一般的带状方程组( 比块三 对角线性方程组更一般的形式) ，并在向量机上实现并行求解，该方法用于块三 对角线性方程组，就得到b o e r 方澍5 6 】。m e i e r 将w a n g 的分割法拓展到带状 方程组c 1 1 ，4 2 1 。也有些并行算法是多种算法的组合，k a p u r 等提出了块三对角线 性方程组的多类型、多阶段组合的并行算法，其中使用了o e r 方法和奇偶消元 法【5 7 1 。l a w r i e 将一般的三对角线性方程组求解方法推广到了正定带状线性代数 方程组，并讨论了计算复杂性和通信复杂性【5 8 1 。i l a n 在m e i e r 的基础上继续改 进分割法，并用来求解正定对称的带状线性代数方程组【”，4 2 l 。l e v i t 将o e r 方法推广到了五对角线性代数方程组删。m e h r m a n n 使用分治策略和一般的分 6 割方法，讨论了一些具体的块三对角线性方程组在分布存储计算环境中的并行 求解算法【6 ”。y a l a m o v 等研究了块o e r 方法的稳定性【础。a l l m a n n 在分布式共 享存储计算机上针对三对角线性代数方程组研究了循环约化法不同编程模型的 运行方案，其中约化和回代过程使用循环约化法，缩减方程组的求解使用r c d 方法，并将这些方法推广到了带状线性代数方程组【6 3 1 。g a r e y 基于矩阵的和分 解讨论了拟对称带状线性代数方程组的并行求解【删。 椭圆型方程、抛物型方程和双曲型方程的数值求解都可以转化成特殊的 t o p e l i t z 块三对角线性方程组的求解，这一问题的串行算法和共享存储计算机上 的并行算法已经有了比较多的研究结果，其中o e r 方法就是h o c k n e y 在研究 p o i s s o n 方程差分格式的求解时提出来的【2 】。b u n e r a a n 提出了数值稳定的直接非 迭代方法( b u n e r n a n 算法) 6 5 1 。b u z b e e 研究了用块三对角o e r 方法直接求解 椭圆型偏微分方程三类定解问题的差分格式【删。d o r r 使用张量积和f o u r i e r 变 换研究p o i s s o n 方程三类定解问题的差分格式，并使用块三对角o e r 方法直接 求解该差分格式【6 刀。b u z b e e 研究了应用规则区域上的几个快速直接方法求解不 规则区域上的p o i s s o n 方程离散格式【碡1 。o n a n a 对于矩形区域上带d i r i c h l e t 边 界条件的椭圆型边值问题的离散格式产生的对称块三对角线性方程组，使用改 进的c h e b y s h e v 多项式和一般的c r a m e r 规则提出了直接求解方法 6 9 1 。s w e e t 研 究了p o i s s o n 方程的离散格式，提出了块元素阶为任意、n 为一般正整数的o e r 方法，并给出了最佳的块元素阶，推广了b u n e r a a n 算法，提出了b u n e m a n 型 o e r 方法的一般形式，其计算方程组右端的算法具有良好的数值稳定性，问题 的总计算量为o ( n 2l o g ，n ) 【7 0 ，7 1 1 。s w a r z t r a u b c r 将求解p o i s s o n 方程的o e r 方法 推广到了求解可分离p o i s s o n 方程三类定解问题的差分格式，计算量为 o ( n m l o g ，疗) ，还提出了一个计算主元的近似多项式方法【7 2 7 3 1 。对于块对角占优 的块三对角线性方程组，h e l l e r 等研究了一般的块o e r 方法，讨论了约化过程 中非主对角元范数的衰型7 4 】。对于p o i s s o n 方程差分格式形成的特殊t o e p l 娩 块三对角线性方程组( 块元素可交换) ，h o c k n e y 结合o e r 方法和f o u r i e r 分 析方法提出了f a c r ( z ) 方法【7 5 1 ；s w a t g 啦u b e r 进一步研究了f a c r ( ，) 方法， 并提出了最优的，值 7 6 】；h e n d r i c k x 则提出了f a c r ( i ) 方法的k r o n e c k e r 积( 张 7 量积) 形式k a c r ( ，) 方法 7 7 】。h o u s t i s 研究了用块o e r 方法求解椭圆型方 程的高精度差分格式，其中用矩阵多项式计算主对角元1 7 8 1 。 上述方法的串行算法已经比较成熟，在共享存储环境中也容易并行实现， 同时也为分布式共享存储环境中的并行算法设计打下了良好的基础。 李晓梅等对于基于f f t 的m d 方法和b u n e m a n 算法的并行实现进行了讨 论【7 9 1 。r o s s i 等在分布式( 包括分布式共享存储