Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers
Arun Jambulapati, Aaron Sidford · Society for Industrial and Applied Mathematics eBooks · 2021
In this paper we provide an O(mloglogO(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 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 > 0 there exist an ultra-sparsifiers with d – 1 + O(d/k) re-weighted vectors of relative condition number at most k2. For small k, this improves upon the previous best known multiplicative factor of k · Õ(log d), which is only known for the graph case.