nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
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.
timing algorithm graph partitioning graph graph sparsification systems accuracy log iter preconditioners