论文标题
Ultrasparse Ultrasparsifiers和更快的Laplacian系统求解器
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers
论文作者
论文摘要
在本文中，我们提供了$ o（m（\ log \ log n）^{o（1）} \ log（1/ε））$ - 预期的时间算法，用于求解$ n $ n $ -node $ m $ - edge图上的laplacian Systems，可改善先前最佳预期运行时的$ O（M \ sqrt fog n}（\ fog n}） N）^{o（1）} \ log（1/ε））$由（Cohen，Kyng，Miller，Pachocki，Peng，Rao，Xu 2014）。为了获得此结果，我们提供了$ \ ell_p $ - 伸展图近似值的有效构造，具有改进的拉伸和稀疏范围。此外，作为这项工作的动力，我们表明，对于$ \ Mathbb {r}^d $中的每组向量（不仅是图形诱导的矢量），并且所有$ k> 1 $都存在$ d-1 + o（d/\ sqrt {k} {k}）$ re-wighted vectors $ d-1 + o（d/\ sqrt {k}）$ re-wighted vectors $ k $ k $ $ k $。对于小$ k $，这在先前最佳的$ \ tilde {o}（\ sqrt {k \ log d}）$的相对相对条件号上有所改善，这仅在图形案例中闻名。
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 \sqrt{\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 $\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.
