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

• 作者: 张慧荣 曹建文
• 来源期刊: 数值计算与计算机应用
• 关键词: 对称对角占优 组合预条件 low-stretch生成树 树分解
• 年，卷（期）: 2015,（4）
• 页码范围: 310-322
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曹建文	中国科学院软件研究所	21	101	6.0	9.0
2	张慧荣	中国科学院软件研究所	2	2	1.0	1.0