Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

In this paper we provide an O(mloglog O(1) n log(1/ ))-expected time algorithm for solving Laplacian systems on n-node m-edge graphs, improving improving upon the previous best expected runtime of O(m √ log nloglog O(1) n log(1/ )) achieved by (Cohen, Kyng, Miller, Pachocki, Peng, Rao, Xu 2014). To obtain this result we provide efficient constructions of ℓ p -stretch graph approximations with improved stretch and sparsity bounds. 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 > 1 there exist ultrasparsifiers with d -1 + O(d/ √ k) re-weighted vectors of relative condition number at most k. For small k, this improves upon the previous best known relative condition number of Õ( √ k log d), which is only known for the graph case.