Computer Science – Data Structures and Algorithms
Scientific paper
2010-03-15
Computer Science
Data Structures and Algorithms
To appear in FOCS 2010
Scientific paper
We present an algorithm that on input of an $n$-vertex $m$-edge weighted graph $G$ and a value $k$, produces an {\em incremental sparsifier} $\hat{G}$ with $n-1 + m/k$ edges, such that the condition number of $G$ with $\hat{G}$ is bounded above by $\tilde{O}(k\log^2 n)$, with probability $1-p$. The algorithm runs in time $$\tilde{O}((m \log{n} + n\log^2{n})\log(1/p)).$$ As a result, we obtain an algorithm that on input of an $n\times n$ symmetric diagonally dominant matrix $A$ with $m$ non-zero entries and a vector $b$, computes a vector ${x}$ satisfying $||{x}-A^{+}b||_A<\epsilon ||A^{+}b||_A $, in expected time $$\tilde{O}(m\log^2{n}\log(1/\epsilon)).$$ The solver is based on repeated applications of the incremental sparsifier that produces a chain of graphs which is then used as input to a recursive preconditioned Chebyshev iteration.
Koutis Ioannis
Miller Gary L.
Peng Richard
No associations
LandOfFree
Approaching optimality for solving SDD systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approaching optimality for solving SDD systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approaching optimality for solving SDD systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-214712