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

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