典型结构大型线性代数方程组的求解剖析.doc

文献综述 1 前言 典型结构大型线性代数方程组的求解是许多应用领域的基础，如：结构分析、电子工程、油藏模拟、计算机辅助几何设计、大气污染研究、化学工程和经济模型模拟、核物理和计算流体力学、数值天气预报等。在数学物理及工程技术领域,如微分方程的求解、多项式插值、网络、系统控制等方面也常会碰到的大型、分块三对角矩阵为系数阵的线性方程组的求解问题。一般，动态过程的数学模型由偏微分方程描述，而偏微分方程的离散化通常导出大型线性方程组，它们可能是对称或非对称的大型稀疏线性方程组，也可能是结构化的大型稀疏线性方程组。甚至于对于依赖于时间的非线性问题，其全局计算的中间步骤也需要对线性方程组的求解。长期以来，伴随着计算环境的不断变化，人们对于求解各类大型线性方程组的适应新的计算环境的新方法的探求从来也没有停止过。目前，分布式存储并行处理机系统己经成为许多科学和工程问题的计算环境，成为求解重大挑战性问题的首选工具；工作站机群(NOWs)和PC机群作为具有良好性价比的分布式存储并行处理机系统已广泛应用于各类科学和工程计算问题。 典型结构大型线性方程组的解法从总体上说可分为直接法和迭代法两大类。求解具有结构化系数矩阵的大型线性方程组的研究近年主要集中在直接法，而迭代法近年来已发展为求解一般大型稀疏线性方程组的主要方法。 本文所研究的内容如下： 考虑大型线性方程组，其中为三对角或块三对角系数矩阵，探讨分布式存储环境下求解大型线性方程组的高效并行算法。 在科学与工程问题中经常遇到的许多微分方程，经过适当差分或有限元离散而形成系数矩阵是块三对角的线性方程组，它们的求解是高性能并行计算的重要课题之一。目前针对求解块三对角线性方程组的并行算法的研究已经有了一些成果，通过对系数矩阵进行分解与近似处理，构造了具有良好的并行性的算法。借助现有的并行工具环境，进一步构造出了并行效率更高的并行求解算法。 2 研究现状 求解典型结构三对角线性代数方程组有多种方法，其解法总体可分为直接法和迭代法两大类。迭代法（iterative methods）[1,2]主要包括Jacobi迭代、Gauss-Seidel迭代、逐次松弛迭代法（SOR），直接法包括高斯消元和几类并行算法。 迭代法 Jacobi迭代因各个分量的修正相互独立而具有十分明显的内在并行计算特性。其主要优点是方法简单，然而它并不常是收敛的，收敛时速度常较慢。在研究如何提高收敛速度的基础上，1983年，Missirlsi提出了并行Jacobi型方法，并讨论了它的收敛性。胡家赣等把它推广到两参数的情形，称之为两参数并行Jacobi型方法[3]。 对于Gauss—Seidel迭代，因充分利用上次求出的新值，可加快收敛速度，正因为每次求值都要用到上次的新值，使它不容易并行。 对于SOR迭代法来说，由于各分量的计算是逐个相关的，因此，一般认为SOR迭代法不适合并行处理，其内在并行性远不如Jacobi迭代。由于SOR多用于有限差分或有限元方法导致的大型稀疏方程组的求解。因此，利用系数矩阵零元素或非零元素的特殊分布，采用红黑或多色排序成为实现SOR并行处理的有效途径。然而，如何找到合适的“彩色模板”并保持自然排序下的收敛速度却是一个问题。蔡放等[4]对SOR方法通过改造提出的向量化SOR算法，在一定条件下具有较好的并行化计算性能。后来，吕全义在文献[5]中对BSOR方法通过改进引入加速因子和松弛因子，使收敛速度相同，但降低了迭代次数。接着，崔喜宁[6]在此基础上，结合方法，将内迭代采用方法，使矩阵的分裂在一定程度上有大的改进，使算法更具灵活性，并行效率也很高。 以上几种基本迭代方法是进行并行迭代的基础，充分了解其并行再借鉴串行算法进行并行程序设计，在这些基础上研究新的算法并重新获得快速的收敛速度。肖曼玉和吕全义在文献[7]中，提出了一种基于Galerkin原理求解块三对角线性方程组的Arnoldi并行算法，通过选取适当的子空间，使算法只在相邻处理机间有通信，因而具有很好的并行性，而且证明了该算法的收敛性。在HPrx2600集群上进行数值计算,结果表明，加速比呈线性增加，并行效率达到90%以上。 直接法 托马斯（Thomas）算法[8]是一种对于三对角线性方程组的特殊的高斯消元方法，也是求解三对角线性方程组首先想到的解法。Thomas算法的求解过程可以概括为两个步骤（removing和backward），首先从前往后依次消去对角线下方的非零元素；再反向回代解出的值，从后往前依次解出所有的未知变量。此算法也容易扩展到块三对角矩阵[9]的应用中。虽然托马斯算法是串行计算机上的最快算法，但由于后面的每一步都要依赖前一步的计算结果，它是不可并行的。 三对角线性方程组和块三对角线性方程组的并行算法，其研究始终非常活跃。总结以往算法，可将其归为