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.
. PRECONDITIONING ALGORITHM for SYMMETRIC DIAGONALLY DOMINANT LINEAR SYSTEMS[J]. Journal of Numerical Methods and Computer Applicat, 2015, 36(4): 310-322.
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.
