Combinatorial Preconditioning

and the solution of linear equations



The combinatorial approach to preconditioning, also called support theory, was introduced by Vaidya in an unpublished paper.  For more information on the history of this field, I recommend Bruce Hendrickson's Support Theory for Preconditioning page.

Shang-Hua Teng and I wrote a large paper on this topic, "Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification and Solving Linear Systems", (prelim version in STOC '04, extended version on arxiv), in which we showed how to solve symmetric, diagonally-dominant linear sytems in nearly-linear time.  We have since broken that paper into three papers, each of which may be read on its own, and which have been submitted to journals individually.
  1. "A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning",
  2. "Spectral Sparsification of Graphs", and
  3. "Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems".
Expositions of the content of these papers may be found in the tutorial I gave at IPCO05 (here are the slides) and in some of the lectures of my class Spectral Graph Theory and its Applications.

Samuel Daitch and I have applied techniques from combinatorial preconditioning in two papers:
Improvements in sparsification have been made in these papers:

Reading List:

Useful for papers 1-3 above:
Other support-theory based algorithms

Mathematical foundations:

Daniel A. Spielman
Last modified: Sept .17, 2008.