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

## Description

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.