Arun Jambulapati: Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

The problem of solving Laplacian linear systems is of central importance to a wide class of recently-developed efficient algorithms for problems on graphs. Starting from the first O(m poly(log n))-time algorithm for solving Laplacian linear systems developed by Spielman and Teng, a sequence of follow-up works have led to much faster and simpler algorithms, culminating in the O(m \sqrt{log n} poly(log log n)) time algorithm of [CKM+14]. However, no further progress on this problem has been obtained since 2014.

In this paper we provide an O(m poly(log log n))-expected time algorithm for solving Laplacian systems on n-node m-edge graphs, setting the complexity of the problem up to poly(log log n) terms. To obtain this result we combine several techniques for constructing well-connected subgraphs to provide efficient constructions of ultrasparse subgraphs with improved stretch and sparsity bounds: as a consequence we improve existing constructions of graph ultrasparsifiers in a large parameter regime. Additionally, as motivation for this work, we show that for every set of vectors in R^d (not just those induced by graphs) and all k>0 there exists ultrasparsifiers with d−1+O(d/k) re-weighted vectors of relative condition number at most k^2. For small k, this improves upon the previous best known multiplicative factor of k⋅Õ (log d), which is only known for the graph case.