Full Title: Nearly-Linear Time Algorithms for Graph Partitioning, Graph
Sparsification,
and Solving Symmetric, Diagonally-Dominant Linear Systems
We combine novel combinatorial algorithms with standard
numerical techniques to obtain an asymptotically fast algorithm for
solving systems of linear equations of the form Ax=b, where A is
symmetric and diagonally dominant.
The combinatorial algorithms are used to build preconditioners, and the
linear systems are solved by a recursive multilevel application of the
preconditioned conjugate gradient.
The algorithm takes time O(m (log^k m) log (1/\epsilon)) to solve a
system with m non-zeros to accuracy epsilon, for some constant k. If
the system is planar, then
the constant k can be reduced to 2. We make no assumptions about A
other than it be diagonally dominant.
The use of combinatorial algorithms to construct preconditioners was
pioneered by Vaidya, who suggested using subgraphs to construct
preconditioners. We construct our subgraphs by augmenting the
low-stretch spanning trees of Elkin, Spielman and Teng.
Our algorithm for augmenting these trees applies a novel algorithm for
graph sparsification. Graph sparsification—the construction of a
sparse subgraph that resembles the original—is an active area of
research in Theoretical Computer Science that turns out to be closely
linked to the problem of preconditioning. We develop nearly-linear time
algorithms for producing sparse subgraphs that are spectrally close to
the original.
Our graph sparsification algorithm relies on a new algorithm for graph
partitioning. It is the first provably fast graph partitioning
algorithm that find sparse cuts of nearly optimal balance. It is based
on a severely truncated diffusion process.
Finally, we will present experimental results demonstrating the power of
these techniques to quickly solve large linear systems.
This is joint work with Shang-Hua Teng.