## 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 relative condition number of G with Ĝ is bounded above by Õ(k log^{2} n), with probability 1-p (we use the Õ() notation to hide a factor of at most (log log n)^{4}). The algorithm runs in time Õ((mlog n+n log^{2} n) log(1/p)). As a result, we obtain an algorithm that on input of an n×n symmetric diagonally dominant matrix A with m nonzero entries and a vector b computes a vector x satisfying ||x-A+b||A <ε|A+b||A, in expected time Õ(mlog^{2} n log(1/ε)). The solver is based on repeated applications of the incremental sparsifier that produces a chain of graphs which is then used as input to the recursive preconditioned Chebyshev iteration.

Original language | English (US) |
---|---|

Pages (from-to) | 337-354 |

Number of pages | 18 |

Journal | SIAM Journal on Computing |

Volume | 43 |

Issue number | 1 |

DOIs | |

State | Published - 2014 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics

## Keywords

- Combinatorial preconditioning
- Graph sparsification
- Iterative solvers
- Symmetric diagonally dominant linear systems