Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

In this paper we provide an O(m (log log n)O(1) 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 n (log log n)O(1) 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 ℝ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 tildeO(√k log d), which is only known for the graph case.