Approaching optimality for solving SDD linear systems
2010
We present an algorithm that on input of an n-vertex m-edge weighted graph G and a value k, produces an incremental sparsifier ˆ G with n−1+m=k edges, such that the condition number of G with ˆ G is bounded above by ˜ O(k log 2 n) 1 , with probability 1 − p. The algorithm runs in time
- Correction
- Cite
- Save
- Machine Reading By IdeaReader
32
References
9
Citations
NaN
KQI