2013/01/28 by Jonathan A. Kelner, Kelner, Jonathan A., Lorenzo Orecchia +5 · 1 citation
Computer Science · Mathematics · #Matrix Theory and Algorithms #Advanced Optimization Algorithms Research #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.1301.6628
In this paper, we present a simple combinatorial algorithm that solves\nsymmetric diagonally dominant (SDD) linear systems in nearly-linear time. It\nuses very little of the machinery that previously appeared to be necessary for\na such an algorithm. It does not require recursive preconditioning, spectral\nsparsification, or even the Chebyshev Method or Conjugate Gradient. After\nconstructing a "nice" spanning tree of a graph associated with the linear\nsystem, the entire algorithm consists of the repeated application of a simple\n(non-recursive) update rule, which it implements using a lightweight data\nstructure. The algorithm is numerically stable and can be implemented without\nthe increased bit-precision required by previous solvers. As such, the\nalgorithm has the fastest known running time under the standard unit-cost RAM\nmodel. We hope that the simplicity of the algorithm and the insights yielded by\nits analysis will be useful in both theory and practice.\n