We present an algorithm that on input of an n-vertex m-edge weighted graph G and a value k produces an incremental sparsifier Ĝ with n-1+m/k edges, such that the relative condition number of G with Ĝ is bounded above by Õ(k log2 n), with probability 1-p (we use the Õ() notation to hide a factor of at most (log log n)4). The algorithm runs in time Õ((mlog n+n log2 n) log(1/p)). As a result, we obtain an algorithm that on input of an n×n symmetric diagonally dominant matrix A with m nonzero entries and a vector b computes a vector x satisfying ||x-A+b||A <ε|A+b||A, in expected time Õ(mlog2 n log(1/ε)). The solver is based on repeated applications of the incremental sparsifier that produces a chain of graphs which is then used as input to the recursive preconditioned Chebyshev iteration.
All Science Journal Classification (ASJC) codes
- Computer Science(all)
- Combinatorial preconditioning
- Graph sparsification
- Iterative solvers
- Symmetric diagonally dominant linear systems