Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

2020/11/17 by Jambulapati, Arun, Sidford, Aaron · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2011.08806

Abstract

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 O(√(k log d)), which is only known for the graph case.

Cited by

• Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
• On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
• Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach

Related

• Subgraph Sparsification and Nearly Optimal Ultrasparsifiers
• Faster Algorithms for Computing the Stationary Distribution, Simulating\n Random Walks, and More
• Eulerian Graph Sparsification by Effective Resistance Decomposition
• Spectral Sparsification of Graphs
• Algorithms and Hardness for Linear Algebra on Geometric Graphs