针对对称对角占优线性系统的组合预条件算法

PRECONDITIONING ALGORITHM for SYMMETRIC DIAGONALLY DOMINANT LINEAR SYSTEMS

本文针对对角占优的对称矩阵(SDD)构成的稀疏线性系统,采用组合预处理技术从谱逼近角度分析并实现一种新型的预条件子.其与ILU类预条件子和AMG类预条件子相比,具有更高的并行可扩展性,满足通量守恒或者等效电阻原理.SDD矩阵通过数学上的规约手段,可以约化为标准的Laplace矩阵,其对应于图论中的无向图.基于此我们首先利用Ofer等提出的算法建立具有low stretch度量的一类生成树.然后采用树分解算法将生成树分解为子树,通过对子树选择合适的连接边进行加边修正得到相应的增广子图.最后将增广子图对应的Laplace矩阵转化为SDD矩阵,该矩阵即为原系数矩阵的预条件子.数值实验表明,与不完全Cholesky分解预条件子相比,该类预条件子更高效,其收敛速度对问题边界类型以及矩阵排序算法不敏感,并且其效率对矩阵规模增长不太敏感.

In this paper, we present a preconditioning algorithm for sparse, symmetric, diagonally- dominant（SDD） linear systems by using combinatorial preconditioning techniques. Compar- ing to incomplete LU factorization preconditioners and AMG preconditioners, combinatorial preconditioners have good parallel scalability. Moreover they meet the flux conservation and quivalent resistance prirmiple. As a SDD matrix can be converted to a Laplacian ma- trix which is isomorphic to an undireceted graph. Based on this fact, we first construct a low stretch spanning tree of the graph corresponding to the SDD coefficient matrix by using Ofer＇s et al algorithm. Then we partition the tree into subtrees based on a tree-decomposition algorithm and add appropriate edges to get an stretch optimized subgraph. Finally, convert the subgraph to a SDD matrix and take it as a preconditioner. We show experimentally that these combinatorial preconditioners are more efficient than incomplete Cholesky factorizationpreconditioners with modification and without modification. Moreover, these combinatorial precontioners are insensitive to the matrix ordering and problem boundary.