数值计算与计算机应用
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  联系我们 |  在线办公 | 
数值计算与计算机应用  2015, Vol. 36 Issue (4): 310-322    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |   
针对对称对角占优线性系统的组合预条件算法
张慧荣, 曹建文
中国科学院软件研究所, 北京 100190
PRECONDITIONING ALGORITHM for SYMMETRIC DIAGONALLY DOMINANT LINEAR SYSTEMS
Zhang Huirong, Cao Jianwen
Institute of Software Sciences, CAS, Beijing 100190, China
 全文: PDF (763 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 本文针对对角占优的对称矩阵(SDD)构成的稀疏线性系统,采用组合预处理技术从谱逼近角度分析并实现一种新型的预条件子.其与ILU类预条件子和AMG类预条件子相比,具有更高的并行可扩展性,满足通量守恒或者等效电阻原理. SDD矩阵通过数学上的规约手段,可以约化为标准的Laplace矩阵,其对应于图论中的无向图.基于此我们首先利用Ofer等提出的算法建立具有low stretch度量的一类生成树.然后采用树分解算法将生成树分解为子树,通过对子树选择合适的连接边进行加边修正得到相应的增广子图.最后将增广子图对应的Laplace矩阵转化为SDD矩阵,该矩阵即为原系数矩阵的预条件子.数值实验表明,与不完全Cholesky分解预条件子相比,该类预条件子更高效,其收敛速度对问题边界类型以及矩阵排序算法不敏感,并且其效率对矩阵规模增长不太敏感.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词对称对角占优   组合预条件   low-stretch生成树   树分解     
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.
Key wordssymmetric diagonally dominant   combinatorial preconditioning   low-stretch spanning tree   tree-decomposition   
收稿日期: 2015-09-05;
基金资助:

国家自然科学基金(91230109)资助项目.

引用本文:   
. 针对对称对角占优线性系统的组合预条件算法[J]. 数值计算与计算机应用, 2015, 36(4): 310-322.
. PRECONDITIONING ALGORITHM for SYMMETRIC DIAGONALLY DOMINANT LINEAR SYSTEMS[J]. Journal of Numerical Methods and Computer Applicat, 2015, 36(4): 310-322.
 
[1] 矩阵计算的理论与方法[M]. 徐树方编著.北京大学出版社, 1995
[2] 数值分析(上册)冯果忱[M]. 黄明游主编. 高等教育出版社, 2007.
[3] 大规模油藏数值模拟并行软件中的高效求解及预处理技术[D]. 博士论文, 2002, 中国科学院软件研究所.
[4] Saad Y. Iterative Methods for Sparse Linear Systems[J]. 2nd edition, SIAM, Philadelphia, PA, 2003.
[5] Hestenes M R and Stiefel E L. Methods of conjugate gradients for solving linear systems[J]. J. Res. Nat. Bur. Stand. 1952, 49:409-436.
[6] Liesen J and Tichy P. Convergence analysis of Krylov subspace methods[J]. GAMM Mitteilungen, 2000, 27(2):153-173.
[7] Axelsson O and Kaporin I. On the sublinear and superlinear rate of convergence of conjugate gradient methods[J]. Numer. Algorithms, 2000, 25:1-22.
[8] Spielman D A and Teng S H. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems[J]. In Proceedings of the thirty-sixth annual ACM Symposium on Theory of Computing, 2004, 81-90.
[9] Spielman D A and Teng S H. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs/cs/0607105, 2006.
[10] Boman EG, Chen D, Parekh O, Toledo S. On factor width and symmetric h-matrices[J]. Linear Algebra and its Applications, 2005, 405:239-248.
[11] Chen D and Toledo S. Vaidya's preconditioners:Implementation and experimental study[J]. Electronic Transactions on Numerical Analysis, 2003, 16:30-49.
[12] Spielman D A and Woo J. A Note on Preconditioning by Low-Stretch Spanning Trees, 2009.
[13] Boman E G and Hendrickson B. Support Theory for Preconditioning[J]. SIAM J. Matrix Anal. Appl., 2003, 25(3):694-717.
[14] Boman E G, Chen D, Hendrickson B and Toledo S. Maximum weight-basis Preconditioners[J]. Numerical Linear Algebra with Applications, 2004, 11:695-721.
[15] Gremban K. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems[D]. PhD thesis, Carnegie Mellon University, CMU-CS-96-123, 1996.
[16] Abraham I and Neiman O. Using petal-decompositions to build a low stretch spanning tree[C]. In Proceedings of the 44th symposium on Theory of Computing, STOC'12, pages 395-406, New York, NY, USA, 2012. ACM.
[17] Vaidya P. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript. A talk based on the manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, Oct 1991.
[18] Spielman D A. Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices[C]. In Proceedings of the International Congress of Mathematicians, 2010.
[19] Koutis I, Miller G L and Peng R. Approaching optimality for solving sdd linear systems[C]. In Foundations of Computer Science (FOCS), 201051st Annual IEEE Symposium on, pages 235-244, 2010.
[20] Koutis I, Miller G L and Peng R. A nearly-mlogn time solver for sdd linear systems[C]. In Foundations of Computer Science (FOCS), 201152nd Annual IEEE Symposium on, 2011, 590-598.
[21] Avron H, Chen D, Shklarski G and Toledo S. Combinatorial Preconditioners for Scalar Elliptic Finite-Element Problems[J]. SIAM Journal on Matrix Analysis and Applications, 2009, 31(2):694-720.
[22] Koutis I, Miller G L and Tolliver D. Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing[J]. Computer Vision and Image Understanding, 2011, 115(12):1638-1646.
[23] Kelner J A, Orecchia L, Sidford A and Zhu Z A. A simple, combinatorial algorithm for solving SDD systems in nearly-linear time[C]. In Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, STOC'13, 2013, 911-920.
没有找到本文相关文献
Copyright © 2008 数值计算与计算机应用 版权所有
中国科学院数学与系统科学研究院 《数值计算与计算机应用》编辑部
北京2719信箱 (100190) Email: szjs@lsec.cc.ac.cn
Support by Beijing Magtech Co.ltd   E-mail:support@magtech.com.cn
京ICP备05002806号-10