In this paper we provide an $O(m (\log \log n)^{O(1)} \log(1/\epsilon))$-expected time algorithm for solving Laplacian systems on $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/\epsilon))$ achieved by (Cohen, Kyng, Miller, Pachocki, Peng, Rao, Xu 2014). To obtain this result we provide efficient constructions of $\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-weighted vectors of relative condition number at most $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.
翻译:本文提供了一种期望运行时间为$O(m (\log \log n)^{O(1)} \log(1/\epsilon))$的算法,用于在$n$个节点,$m$条边的图中求解Laplacian系统,改进了(Cohen,Kyng,Miller,Pachocki,Peng,Rao,Xu 2014)的最佳期望运行时间$O(m \sqrt{\log n} (\log \log n)^{O(1)} \log(1/\epsilon))$。为了得到这个结果,我们提供了具有改进的Stretch和稀疏度界限的$\ell_p$-Stretch图近似的有效构造。此外,作为对这项工作的动机,我们展示了对于$\mathbb{R}^d$中的每个向量集合(不仅仅是由图引发的),以及所有$k>1$,都存在具有$d-1+O(d/\sqrt{k})$个重新加权向量以及相对条件数为$k$的Ultrasparsifiers。当$k$很小时,这比以前所知的最佳相对条件数$\tilde{O}(\sqrt{k \log d})$更好,而这仅为图形情况所知。