Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

In this paper we provide an $O(m (\log \log n)^{O(1)} \log(1/\epsilon))$-expectedtimealgorithmforsolvingLaplaciansystemson$n$-node$m$-edge graphs, improving improving upon the previous best expected runtime of $O(m\sqrt{\log n}(\log \log n{)}^{O(1)}\log (1\mathrm{/}ϵ))$ achieved by (Cohen, Kyng, Miller, Pachocki, Peng, Rao, Xu 2014). To obtain this result we provide efficient constructions of ${\mathrm{\ell }}_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 ${\mathbb{R}}^d$ (not just those induced by graphs) and all $k>1$ there exist ultrasparsifiers with $d-1 + O(d/\sqrt{k})$re-weightedvectorsofrelativeconditionnumberatmost$k$. For small $k$, this improves upon the previous best known relative condition number of $\tilde{O}(\sqrt{k\log d})$, which is only known for the graph case.