Institutional Repository
| 针对对称对角占优线性系统的组合预条件算法 | |
| Alternative Title | PRECONDITIONING ALGORITHM for SYMMETRIC DIAGONALLY DOMINANT LINEAR SYSTEMS |
| 张慧荣; 曹建文 | |
| 2015 | |
| Source | 数值计算与计算机应用
 |
| ISSN | 1000-3266 |
| Volume | 36Issue:4Pages:310-322 |
| English Abstract | 本文针对对角占优的对称矩阵(SDD)构成的稀疏线性系统,采用组合预处理技术从谱逼近角度分析并实现一种新型的预条件子.其与ILU类预条件子和AMG 类预条件子相比,具有更高的并行可扩展性,满足通量守恒或者等效电阻原理.SDD矩阵通过数学上的规约手段,可以约化为标准的Laplace矩阵,其对应 于图论中的无向图.基于此我们首先利用Ofer等提出的算法建立具有low stretch度量的一类生成树.然后采用树分解算法将生成树分解为子树,通过对子树选择合适的连接边进行加边修正得到相应的增广子图.最后将增广子图对 应的Laplace矩阵转化为SDD矩阵,该矩阵即为原系数矩阵的预条件子.数值实验表明,与不完全Cholesky分解预条件子相比,该类预条件子更高 效,其收敛速度对问题边界类型以及矩阵排序算法不敏感,并且其效率对矩阵规模增长不太敏感. |
| Indexed Type | CSCD |
| Abstract | In this paper, we present a preconditioning algorithm for sparse, symmetric, diagonally-dominant (SDD) linear systems by using combinatorial preconditioning techniques. Comparing to incomplete LU factorization preconditioners and AMG preconditioners, combinatorial preconditioners have good parallel scalability. Moreover they meet the flux conservation and quivalent resistance principle. As a SDD matrix can be converted to a Laplacian matrix 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 factorization preconditioners with modification and without modification. Moreover, these combinatorial precontioners are insensitive to the matrix ordering and problem boundary. |
| Keyword | 对称对角占优 组合预条件 Low-stretch生成树 树分解 |
| Department | 张慧荣, 中国科学院软件研究所, 北京 100190, 中国;曹建文, 中国科学院软件研究所, 北京 100190, 中国; |
| Language | 中文 |
| CSCD ID | CSCD:5588729 |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/17386 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | 张慧荣,曹建文. 针对对称对角占优线性系统的组合预条件算法[J]. 数值计算与计算机应用,2015,36(4):310-322. |
| APA | 张慧荣,&曹建文.(2015).针对对称对角占优线性系统的组合预条件算法.数值计算与计算机应用,36(4),310-322. |
| MLA | 张慧荣,et al."针对对称对角占优线性系统的组合预条件算法".数值计算与计算机应用 36.4(2015):310-322. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment