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.

Authors

• Daniel A. Spielman
• Shang-Hua Teng

Keywords

• graph partitioning
• graph sparsification
• preconditioners