We present a randomized algorithm that, on input a symmetric, weakly diagonally dominant n-by-n matrix A with m non-zero entries and an n-vector b, produces anx such that The algorithm applies subgraph preconditioners in a recursive fashion. These preconditioners improve upon the subgraph preconditioners first introduced by Vaidya (1990) . For any symmetric, weakly diagonally-dominant matrix A with non-positive off-diagonal entries and k ≥ 1, we construct in time m log O(1) n a preconditioner of A with at most non-zero off-diagonal entries such that the finite generalized condition number κ f (A, B) is at most k. If the non-zero structure of the matrix is planar, then the condition number is at most O (n/k) log n log log 2 n , and the corresponding linear system solver runs in expected time O(n log 2 n + n log n (log log n) 2 log(1/ǫ)). Similar bounds are obtained on the running time of algorithms computing approximate Fiedler vectors. * This paper is the last in a sequence of three papers expanding on material that appeared first under the title "Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems" [ST04]. The second paper, "Spectral Sparsification of Graphs" [ST08c] contains algorithms for constructing sparsifiers of graphs, which we use in this paper to build preconditioners. The first paper, "A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning" [ST08b] contains graph partitioning algorithms that are used to construct sparsifiers in the second paper.
Spielman and Teng present a nearly-linear time algorithm for preconditioning and solving symmetric diagonally dominant matrices, including those of graph Laplacians REF .
Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
ArXiv
ArXiv
Computer Science Mathematics