中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 期刊论文
Title:
针对对称对角占优线性系统的组合预条件算法
Alternative Title: PRECONDITIONING ALGORITHM for SYMMETRIC DIAGONALLY DOMINANT LINEAR SYSTEMS
Author: 张慧荣 ; 曹建文
Keyword: 对称对角占优 ; 组合预条件 ; low-stretch生成树 ; 树分解
Source: 数值计算与计算机应用
Issued Date: 2015
Volume: 36, Issue:4, Pages:310-322
Indexed Type: CSCD
Department: 张慧荣, 中国科学院软件研究所, 北京 100190, 中国;曹建文, 中国科学院软件研究所, 北京 100190, 中国;
Abstract: 本文针对对角占优的对称矩阵(SDD)构成的稀疏线性系统,采用组合预处理技术从谱逼近角度分析并实现一种新型的预条件子.其与ILU类预条件子和AMG 类预条件子相比,具有更高的并行可扩展性,满足通量守恒或者等效电阻原理.SDD矩阵通过数学上的规约手段,可以约化为标准的Laplace矩阵,其对应 于图论中的无向图.基于此我们首先利用Ofer等提出的算法建立具有low stretch度量的一类生成树.然后采用树分解算法将生成树分解为子树,通过对子树选择合适的连接边进行加边修正得到相应的增广子图.最后将增广子图对 应的Laplace矩阵转化为SDD矩阵,该矩阵即为原系数矩阵的预条件子.数值实验表明,与不完全Cholesky分解预条件子相比,该类预条件子更高 效,其收敛速度对问题边界类型以及矩阵排序算法不敏感,并且其效率对矩阵规模增长不太敏感.
English 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.
Language: 中文
Citation statistics:
Content Type: 期刊论文
URI: http://ir.iscas.ac.cn/handle/311060/17386
Appears in Collections:软件所图书馆_期刊论文

Files in This Item:

There are no files associated with this item.


Recommended Citation:
张慧荣,曹建文. 针对对称对角占优线性系统的组合预条件算法[J]. 数值计算与计算机应用,2015-01-01,36(4):310-322.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[张慧荣]'s Articles
[曹建文]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[张慧荣]‘s Articles
[曹建文]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2019  中国科学院软件研究所 - Feedback
Powered by CSpace