Research on Solving Linear Systems

Shang-Hua Teng and I have written two conference papers on solving symmetric, diagonally dominant systems of linear equations. At the moment, the best paper to read on our work is:

Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems.

This paper contains the numerically interesting part of our monstor paper:

Nearly linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

A second paper containing the combinatorially interesting part is in preparation. We have split this paper into two to facilitate refereeing and reading by different communities. The numerical paper complete subsumes our first conference paper on this topic:

Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O (m^{1.31})

Daniel A. Spielman