Finding effective support-tree preconditioned
In 1995, Gremban, Miller, and Zagha introduced support-tree preconditioners and a parallel algorithm called supporttree conjugate gradient (STCG) for solving linear systems of the form Ax = b, where A is an n × 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 4 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∈V c(v) 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). Copyright 2005 ACM.
Maggs, BM; Miller, GL; Parekh, O; Ravi, R; Woo, SLM
Annual Acm Symposium on Parallelism in Algorithms and Architectures
Start / End Page
Digital Object Identifier (DOI)