Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
2004pp. 81–90
Citations Over TimeTop 1% of 2004 papers
Abstract
We present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where κf (A) is the condition number of the matrix defining the linear system. Our algorithm applies the preconditioned Chebyshev iteration with preconditioners designed using nearly-linear time algorithms for graph sparsification and graph partitioning.
Related Papers
- → Notes on matrices with diagonally dominant properties(2011)7 cited
- Two Subsets of Nonsingular H-Matrix(2006)
- Simple Criteria for Nonsingular H-Matrices(2005)
- Local α-Doubly Diagonally Dominance and Sufficent Conditions for Nonsingular H-Matrix(2007)
- Locally Double α-diagonally Dominant Matrix and its Applications(2005)