Finding effective support-tree preconditioners

In 1995, Gremban, Miller, and Zagha introduced support-tree preconditioners and a parallel algorithm called support-tree conjugate gradient (STCG) for solving linear systems of the form Ax = b, where A is an n x n Laplacian matrix. A Laplacian is a symmetric matrix in which the off-diagonal entries are non-positive, and the row and column sums are zero. A Laplacian A with 2m off-diagonal non-zeros can be interpreted as an undirected positively-weighted graph G with n vertices and m edges, where there is an edge between two vertices i and j with weight c((i,j)) = --A_i,j = --A_j,i if A_i,j = A_j,i ‹ 0. Gremban et al showed experimentally that STCG performs well on several classes of graphs commonly used in scientific computations. In his thesis, Gremban also proved upper bounds on the number of iterations required for STCG to converge for certain classes of graphs. In this paper, we present an algorithm for finding a preconditioner for an arbitrary graph G = (V,E) with n vertices, m edges, and a weight function c › 0 on the edges, where w.l.o.g., min_e∈e c(e) = 1. Equipped with this preconditioner, STCG requires O(log⁴ n · √Δ/α) iterations, where α = min_{U⊂V,|U|≤|V|/2} c(U,V\U)/|U| is the minimum edge expansion of the graph, and Δ = max_υ∈V c(υ) is the maximum incident weight on any vertex. Each iteration requires O(m) work and can be implemented in O(log n) steps in parallel, using only O(m) space. Our results generalize to matrices that are symmetric and diagonally-dominant (SDD).