Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We present an algorithm that on input a graph $G$ with $n$ vertices and $m+n-1$ edges 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 $ ilde{O}(klog^2 n)$, with probability $1-p$. The algorithm runs in time

$$ ilde{O}((m log{n} + nlog^2{n})log(1/p)).$$

As a result, we obtain an algorithm that on input an $n imes n$ symmetric diagonally dominant matrix $A$ with $m+n-1$ non-zero entries and a vector $b$, computes a vector $ar{x}$ satisfying $||x-A^{+}b||_A<epsilon ||A^{+}b||_A $, in time

$$ ilde{O}(mlog^2{n}log(1/epsilon)).$$

The solver is based on a recursive application of the incremental sparsifier that produces a hierarchy of graphs which is then used to construct a recursive preconditioned Chebyshev iteration.

Questions and Answers

You need to be logged in to be able to post here.