A BLOCK PROJECTION METHOD FOR SPARSE MATRICES
A BLOCK PROJECTION METHOD FOR SPARSE MATRICES
复制标题
DOI：
10.1137/0913003
复制
发表时间：
1992-01-01
期刊：
影响因子：
--
通讯作者：
RUIZ, D
中科院分区：
文献类型：
--
作者：
ARIOLI, M;DUFF, I;RUIZ, D
描述了求解一般一致稀疏线性方程组的Cimmino算法的块版本。强调块三对角线形式矩阵的情况，因为假定一般情况可以通过置换简化为这种形式。说明了如何使用共轭梯度（CG）算法加速基本方法。这种加速非常依赖于原始系统的分区，并讨论了几种可能的分区。在增广系统上，利用Harwell稀疏对称不定解器MA27求解了分划系统的子问题所对应的欠定系统。这些系统是独立的，可以并行求解。对共轭梯度加速度的迭代矩阵的分析导致考虑到相当不寻常的和新颖的矩阵缩放，改变迭代矩阵的谱以减少CG迭代的次数。该算法的各个方面已经在一个8处理器的Alliant FX/80上在四个块三对角线系统上进行了测试，其中两个来自流体动力学模拟，两个来自文献。研究了分区和缩放对迭代次数和求解总耗时的影响。在所有情况下，都能得到快速收敛的精确解。
A block version of Cimmino's algorithm for solving general sets of consistent sparse linear equations is described. The case of matrices in block tridiagonal form is emphasized because it is assumed that the general case can be reduced to this form by permutations. It is shown how the basic method can be accelerated by using the conjugate gradient (CG) algorithm. This acceleration is very dependent on a partitioning of the original system and several possible partitionings are discussed. Underdetermined systems corresponding to the subproblems of the partitioned system are solved using the Harwell sparse symmetric indefinite solver MA27 on an augmented system. These systems are independent and can be solved in parallel. An analysis of the iteration matrix for the conjugate gradient acceleration leads to the consideration of rather unusual and novel scalings of the matrix that alter the spectrum of the iteration matrix to reduce the number of CG iterations.The various aspects of this algorithm have been tested by runs on an eight-processor Alliant FX/80 on four block tridiagonal systems, two from fluid dynamics simulations and two from the literature. The effect of partitioning and scaling on the number of iterations and overall elapsed time for solution is studied. In all cases, an accurate solution with rapid convergence can be obtained.