http://arxiv.org/abs/1301.6628 Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu: A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time (Submitted on 28 Jan 2013) In this paper, we present a simple combinatorial algorithm that solves symmetric diagonally dominant (SDD) linear systems in nearly-linear time. --They reduce the problem to solving Poisson's equation on a graph. which is, essentially, a circuit made of resistors and each node attached to a current source. Task is to find all the voltages. The solve method is to repeatedly randomly sample a cycle from the set of cycles in the graph (under a certain probability distribution) and then modify to make the total current flowing round the cycle become 0. Near linear runtime bounds are proved. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)