Solving Symmetric Diagonally-Dominant Systems by Preconditioning
Bruce MacDowell Maggs, Gary Lee Miller, Ojas Parekh, R. Ravi, Shan Leung, Maverick Woo · 2003
In this paper we design support-tree preconditioners for n × n matrices with m nonzeros that are symmetric and diagonally-dominant with a nonnegative diagonal (SDD matrix). This reduces to designing such a preconditioner for a Laplacian matrix, A, which can be interpreted as an undirected nonnegatively-weighted graph, G with n vertices and m edges. Preconditioners accelerate the convergence of iterative methods for solving linear systems, and our preconditioner allows us to analyze the convergence of a particular algorithm, due to Gremban and Miller, called support-tree conjugate gradient (STCG). An advantage of support-tree preconditioners is that STCG parallelizes well. We show that STCG equipped with our preconditioner requires O(m log 2 n · � dilexp(G)) work and O(m) space to solve the system Ax = b, where dilexp(G) is an edge-expansion-based upper bound on the diameter of G. Existing bounds depend only on the size of the matrix (graph), hence our bound is incomparable. For instance, if G is a bounded-degree expander graph with uniform edge weights, dilexp(G) = O(log 2 n), and the work is O(n log 3 n). This is currently the best known bound for Laplacians of expander graphs. We show that dilexp(G) is always at most n, hence our bound is at most O(m √ n log 2 n) for any Laplacian (or SDD) matrix. For sufficiently dense systems, when m = Ω(n 1.61), this bound offers the best known work guarantee of any linear-space method. The main technical contributions of this paper include (i) adapting a recent result of Räcke to designing support-tree preconditioners, (ii) extending a power dissipation approach for bounding support numbers of preconditioners, and (iii) applying the methods used in Leighton and Rao’s approximate max-flow min-cut theorem to the “asymmetric” product flows the arise in Räcke’s construction.