求解三对角线性方程组两类并行算法的特点.doc

求解三对角线性方程组两类并行算法的特点 一、概述 三对角线性方程组的求解是许多科学和工程计算中最重要也是最基本的问题之一在核物理、流体力学、油藏工程、石油地震数据处理及数值天气预报等许多领域的大规模科学工程和数值处理中都会遇到三对角系统的求解问题很多三对角线性方程组的算法可以直接推广到求解块三对角及带状线性方程组由于在理论和实际应用上的重要性近20年来三对角方程组的并行算法研究十分活跃 大规模科学计算需要高性能的并行计算机随着软硬件技术的发展高性能的并行计算机日新月异现今smp可构成每秒几十亿次运算的系统pvp和cow可构成每秒几百亿次运算的系统而mpp和dsm可构成每秒万亿次运算或更高的系统 高性能并行计算机只是给大型科学计算提供了计算工具如何发挥并行计算机的潜在性能和对三对角系统进行有效求解其关键在于抓住并行计算的特点进行并行算法的研究和程序的设计与实现另外对处理机个数较多的并行计算系统在设计并行算法时必须解决算法的可扩展性并对可扩展性进行研究和分析 二、问题的提出 设三对角线性方程组为 ax=y（1） 式中：arnn非奇异ij=0x=(x1x2xn)ty=(y1y2yn）t 此系统在许多算法中被提出因此研究其高性能并行算法是很有理论和实际意义的 三、并行求解三对角系统的直接解法 关于三对角线性方程组的直接求解已经有大量并行算法其中wang的分裂法是最早针对实际硬件环境基于分治策略提出的并行算法它不仅通信结构简单容易推广到一般带状线性方程组的并行求解而且为相继出现的许多其它并行算法提供了可行的局部分解策略 近20年来求解三对角方程组的并行算法都是基于分治策略即通过将三对角方程组分解成p个小规模问题求解这p个小规模问题再将这些解结合起来得到原三对角方程组的解一般求解三对角方程组的分治方法的计算过程可分为3个阶段：一是消去每台处理机对子系统消元；二是求解缩减系统（需要通信）；三是回代将缩减系统的解回代到每个子系统求出最终结果具体可分为以下几类： （一）递推耦合算法（recursivedoubling） 由stone于1975年提出算法巧妙地把lu分解方法的时序性很强的递推计算转化为递推倍增并行计算d.j.evans对此方法做了大量研究p.dubois和g.rodrigue的研究表明stone算法是不稳定的 （二）循环约化方法（cyclicreduction） 循环约化方法由hockey和g.golub在1965年提出其基本思想是每次迭代将偶数编号方程中的奇变量消去只剩下偶变量问题转变成求解仅由偶变量组成的规模减半的新三对角方程组求解该新方程组得到所有的偶变量后再回代求解所有的奇变量即约化和回代过程由于其基本的算术操作可以向量化适合于向量机此方法有大量学者进行研究提出了许多改进的方法例如heller针对最后几步的短向量操作提出了不完全循环约化方法；r.reulter结合ibm3090vf向量机的特点提出了局部循环约化法；p.amodio针对分布式系统的特点改进了循环约化方法；最近针对此方法又提出对三对角方程组进行更大约化步的交替迭代策略 （三）基于矩阵乘分解算法 将系数矩阵a分解成a=ft方程ax=b化为fy=b和tx=y两个方程组的并行求解这种算法又可以分为两类： 1.重叠分解如wang的分裂法及其改进算法就属于这一类p.amodio在1993年对这类算法进行了很好的总结用本地lu、本地lud和本地循环约化法求解并在1995年提出基于矩阵乘分解的并行qr算法h.michielse和a.vandervorst改变wang算法的消元次序提出了通信量减少的算法李晓梅等将h.michielse和a.vandervorst算法中的通信模式从单向串行改为双向并行提出dpp算法是目前最好的三对角方程组分布式算法之一XX年骆志刚等中依据dpp算法利用计算与通信重叠技术减少处理机空闲时间取得了更好的并行效果此类算法要求解p1阶缩减系统 2.不重叠分解例如lawriesameh算法、johsoon算法、baron算法、chawla在1991年提出的wz分解算法以及mattor在1995年提出的算法都属于这一类此类算法要求解2p2阶缩减系统 （四）基于矩阵和分解算法 将系数矩阵分解成a=ao+a这类算法的共同特点是利用shermanmorrison公式将和的逆化为子矩阵逆的和按矩阵分解方法这种算法又可分为两类： 1.重叠分解这类算法首先由mehrmann在1990年提出通过选择好的分解在计算过程中保持原方程组系数矩阵的结构特性具有好的数值稳定性需要求解p1阶缩减系统 2.不重叠分解sun等在1992年提出的并行划分lu算法ppt算法和并行对角占优算法pdd算法均属于这一类需要求解2p2阶缩减系统其中pdd算法的通讯时间不随处理机的变化而变化具有很好的可扩展性x.h.sun和w.zhang在XX年提出了两层混合并行方法pth其基本思想是在pdd中嵌入一个内层三对角解法以形成一个两层的并行基本算法是pdd三对角系统首先基于pdd分解pth算法也具有很好的可扩展性 四、并行求解三对角系统的迭代解法 当稀疏线性方程组的系数矩阵不规则时直接法在求解过程中会带来大量非零元素增加了计算量、通信量和存储量并且直接法不易并行不能满足求解大规模问题的需要因此通常使用迭代法来求解一般系数线性方程组和含零元素较多三对角线性方程组迭代法包括古典迭代法和krylov子空间迭代法 古典迭代法包括jacobi、gaussseidel、sor、ssor等方法通常采用红黑排序、多色排序和多分裂等技术进行并行计算 由于古典迭代法有收敛速度慢、并行效果不好等缺点目前已较少用于直接求解大型稀疏线性方程组而是作为预条件子和其它方法（如krylov子空间方法）相结合使用krylov子空间方法具有存储量小计算量小且易于并行等优点非常适合于并行求解大型稀疏线性方程组结合预条件子的krylov子空间迭代法是目前并行求解大型稀疏线性方程组的最主要方法 给定初值x0求解稀疏线性方程组ax=y设km为维子空间一般投影方法是从m维仿射子空间x0+km中寻找近似解xm使之满足petrovgalerkin条件 yaxmlm 其中lm为另一个维子空间如果km是krylov子空间则上述投影方法称为krylov子空间方法krylov子空间km(ar0)定义为： km(ar0)=spanr0ar0a2r0am1r0 选取不同的km和lm就得到不同的krylov子空间方法主要算法包括四类：基于正交投影方法、基于正交化方法、基于双正交化方法、基于正规方程方法 krylov子空间迭代法的收敛速度依赖于系数矩阵特征值的分布对于很多问题直接使用迭代法的收敛速度特别慢或者根本不收敛因此使用预条件改变其收敛性使中断问题可解并加速收敛速度是需要的目前人们研究的预条件技术可分为四类：采用基于矩阵分裂的古典迭代法作为预条件子、采用不完全lu分解作预条件子、基于系数矩阵近似逆的预条件子、结合实际问题用多重网格或区域分解作预条件子对krylov子空间和预条件krylov子空间方法有详细的讨论 预条件krylov子空间方法的并行计算问题一直是研究热点已提出了一系列好的并行算法目前预条件krylov子空间方法的计算量主要集中在矩阵向量乘上虽然学者们做了大量的研究工作但是还没找到效果好又易于并行的预条件子 需要特别指出的是对于一般线性代数方程组的并行求解其可扩展并行计算的研究已相对成熟并已形成相应的并行软件库如美国田纳西亚州立大学和橡树岭国家实验室研制的基于消息传递计算平台的可扩展线性代数程序库scalapack和得克萨斯大学开发的界面更加友好的并行线性代数库plapack我们借鉴其研究成果和研究方法对三对角线性方程组并行算法的研究是有帮助的 五、结语 三对角线性方程组的直接解法算法丰富程序较容易实现但计算过程要增加计算量并且大部分算法都对系数矩阵的要求比较高迭代解法适合于非零元素较多的情况特别是结合预条件子的krylov子空间迭代法已成为当前研究的热点 尽管三对角系统并行算法的研究取得了很多成果但是还存在一些问题：直接法中分治策略带来计算量和通信量的