Spectral graph sparsification Part 2: [An O(mlog^2 n) algorithm for solving SDD systems]

Опубликовано 17 августа 2016, 22:01

We present the fastest known algorithm for solving symmetric diagonally dominant (SDD) systems. If the number of the non-zeros in the system matrix is m, and the desired error is err, the algorithm runs in time O(mlog^2 m log(1/err) ). The heart of the algorithm is a spectral sparsification algorithm, which on an input of a graph A with n nodes and m edges returns a graph B with n-1+m/k edges, such that for all real vectors x, 1 (x^T B x)/(x^T A x) O(klog^2 n). The algorithm is randomized and runs in O(mlog^2 n) expected time. It is based on a simple and practical sampling procedure of independent interest. The sparsification algorithm and the solver simplify greatly the groundbreaking work of Spielman and Teng who were the first to design nearly linear time algorithms for SDD systems. Joint work with Gary Miller and Richard Peng