针对对称对角占优线性系统的组合预条件算法
文献类型：期刊论文
| 作者 | 张慧荣 ; 曹建文 |
| 刊名 | 数值计算与计算机应用
 |
| 出版日期 | 2015 |
| 卷号 | 36期号:4页码:310-322 |
| 关键词 | 对称对角占优 组合预条件 low-stretch生成树 树分解 |
| ISSN号 | 1000-3266 |
| 其他题名 | 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. 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. |
| 收录类别 | CSCD |
| 语种 | 中文 |
| CSCD记录号 | CSCD:5588729 |
| 公开日期 | 2016-12-09 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/17386]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | 张慧荣,曹建文. 针对对称对角占优线性系统的组合预条件算法[J]. 数值计算与计算机应用,2015,36(4):310-322. |
| APA | 张慧荣,&曹建文.(2015).针对对称对角占优线性系统的组合预条件算法.数值计算与计算机应用,36(4),310-322. |
| MLA | 张慧荣,et al."针对对称对角占优线性系统的组合预条件算法".数值计算与计算机应用 36.4(2015):310-322. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。