评价网 > 科教论文 > 理学毕业论文 > 数学论文 > 正文

当前求解三对角线性方程组两类并行算法的特点(2)

2013-07-05 01:01
　　当稀疏线性方程组的系数矩阵不规则时，直接法在求解过程中会带来大量非零元素，增加了计算量、通信量和存储量，并且直接法不易并行，不能满足求解大规模问题的需要。因此通常使用迭代法来求解一般系数线性方程组和含零元素较多三对角线性方程组。迭代法包括古典迭代法和Krylov子空间迭代法。
　　古典迭代法包括Jacobi、Gauss-Seidel、SOR、SSOR等方法。通常采用红黑排序、多色排序和多分裂等技术进行并行计算。

　　由于古典迭代法有收敛速度慢、并行效果不好等缺点，目前已较少用于直接求解大型稀疏线性方程组，而是作为预条件子和其它方法（如Krylov子空间方法）相结合使用。
　　Krylov子空间方法具有存储量小，计算量小且易于并行等优点，非常适合于并行求解大型稀疏线性方程组。结合预条件子的Krylov子空间迭代法是目前并行求解大型稀疏线性方程组的最主要方法。
　　给定初值X0，求解稀疏线性方程组AX=Y。设Km为维子空间，一般投影方法是从m维仿射子空间X0+Km中寻找近似解Xm使之满足Petrov-Galerkin条件
　　　　　　　　Y-AXm┻Lm　　　　　
      其中Lm为另一个维子空间。如果Km是Krylov子空间，则上述投影方法称为Krylov子空间方法。Krylov子空间Km(A，r0)定义为：
　　     Km(A，r0)=span{r0，Ar0，A2r0，…，Am-1r0}
      选取不同的Km和Lm就得到不同的Krylov子空间方法。主要算法包括四类：基于正交投影方法、基于正交化方法、基于双正交化方法、基于正规方程方法。
　　Krylov子空间迭代法的收敛速度依赖于系数矩阵特征值的分布，对于很多问题，直接使用迭代法的收敛速度特别慢，或者根本不收敛。因此使用预条件改变其收敛性，使中断问题可解，并加速收敛速度是需要的。目前人们研究的预条件技术可分为四类：采用基于矩阵分裂的古典迭代法作为预条件子、采用不完全LU分解作预条件子、基于系数矩阵近似逆的预条件子、结合实际问题用多重网格或区域分解作预条件子。对Krylov子空间和预条件Krylov子空间方法有详细的讨论。 （科教范文网 Lw.nsEAc.com编辑整理）
　　预条件Krylov子空间方法的并行计算问题一直是研究热点，已提出了一系列好的并行算法。目前预条件Krylov子空间方法的计算量主要集中在矩阵向量乘上。虽然学者们做了大量的研究工作，但是还没找到效果好，又易于并行的预条件子。
　　需要特别指出的是，对于一般线性代数方程组的并行求解，其可扩展并行计算的研究已相对成熟，并已形成相应的并行软件库，如美国田纳西亚州立大学和橡树岭国家实验室研制的基于消息传递计算平台的可扩展线性代数程序库ScaLAPACK和得克萨斯大学开发的界面更加友好的并行线性代数库PLAPACK。我们借鉴其研究成果和研究方法，对三对角线性方程组并行算法的研究是有帮助的。
　　五、结语
　　三对角线性方程组的直接解法，算法丰富，程序较容易实现。但计算过程要增加计算量，并且大部分算法都对系数矩阵的要求比较高。迭代解法适合于非零元素较多的情况，特别是结合预条件子的Krylov子空间迭代法已成为当前研究的热点。
　　尽管三对角系统并行算法的研究取得了很多成果。但是还存在一些问题：直接法中，分治策略带来计算量和通信量的增加，如何减少计算量和通信量有待于进一步的研究；目前直接算法均基于分治策略，如何把其它并行算法设计技术，如平衡树和流水线等技术应用到三对角系统的并行求解中也是需要引起重视的方向；对于非对称系统还没找到一种通用的Krylov子空间方法；Krylov子空间方法的并行实现时仅考虑系数矩阵与向量乘，对其它问题考虑不够；以往设计的并行算法缺乏对算法可扩展性的考虑和分析。

【参考文献】
　　[1]骆志刚，李晓梅，王正华.三对角线性方程组的一种有效分布式并行算法[J].计算机研究与发展，2000，（7）