Skip to main content

Finding effective support-tree preconditioned

Publication ,  Journal Article
Maggs, BM; Miller, GL; Parekh, O; Ravi, R; Woo, SLM
Published in: Annual ACM Symposium on Parallelism in Algorithms and Architectures
December 1, 2005

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.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Annual ACM Symposium on Parallelism in Algorithms and Architectures

DOI

Publication Date

December 1, 2005

Start / End Page

176 / 185
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Maggs, B. M., Miller, G. L., Parekh, O., Ravi, R., & Woo, S. L. M. (2005). Finding effective support-tree preconditioned. Annual ACM Symposium on Parallelism in Algorithms and Architectures, 176–185. https://doi.org/10.1145/1073970.1073996
Maggs, B. M., G. L. Miller, O. Parekh, R. Ravi, and S. L. M. Woo. “Finding effective support-tree preconditioned.” Annual ACM Symposium on Parallelism in Algorithms and Architectures, December 1, 2005, 176–85. https://doi.org/10.1145/1073970.1073996.
Maggs BM, Miller GL, Parekh O, Ravi R, Woo SLM. Finding effective support-tree preconditioned. Annual ACM Symposium on Parallelism in Algorithms and Architectures. 2005 Dec 1;176–85.
Maggs, B. M., et al. “Finding effective support-tree preconditioned.” Annual ACM Symposium on Parallelism in Algorithms and Architectures, Dec. 2005, pp. 176–85. Scopus, doi:10.1145/1073970.1073996.
Maggs BM, Miller GL, Parekh O, Ravi R, Woo SLM. Finding effective support-tree preconditioned. Annual ACM Symposium on Parallelism in Algorithms and Architectures. 2005 Dec 1;176–185.

Published In

Annual ACM Symposium on Parallelism in Algorithms and Architectures

DOI

Publication Date

December 1, 2005

Start / End Page

176 / 185