Carnegie Mellon University
Browse

Approaching Optimality For Solving SDD Linear Systems

Download (213.87 kB)
journal contribution
posted on 2003-01-01, 00:00 authored by Ioannis Koutis, Gary Miller, Richard Peng
Abstract—We present an algorithm that on input of an n-vertex m-edge weighted graph G and a value k, produces an incremental sparsifier Ĝ with n-1+m=k edges, such that the condition number of G with Ĝ is bounded above by Õ(k log2 n), with probability 1 - p.

History

Date

2003-01-01

Usage metrics

    Categories

    Keywords

    algorithms; spectral graph theory; linear systems; combinatorial preconditioningInformation and Computing Sciences not elsewhere classified

    Licence

    In Copyright

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC