SCIENCE@home

Approaching Optimality for Solving SDD Linear Systems

I. Koutis,G. Miller,Richard Peng

Published 2010 in IEEE Annual Symposium on Foundations of Computer Science

ABSTRACT

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

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-51 of 51 references · Page 1 of 1

CITED BY

Showing 1-100 of 272 citing papers · Page 1 of 3

123
Next