Algorithms achieve almost-linear time for ℓ_p-norm flow and dual regression problems on unit-weighted graphs for a range of p, plus applications to max-flow and total variation.
A nearly-mlogn time solver for SDD linear systems
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
We present an improved algorithm for solving symmetrically diagonally dominant linear systems. On input of an $n\times n$ symmetric diagonally dominant matrix $A$ with $m$ non-zero entries and a vector $b$ such that $A\bar{x} = b$ for some (unknown) vector $\bar{x}$, our algorithm computes a vector $x$ such that $||{x}-\bar{x}||_A < \epsilon ||\bar{x}||_A $ {$||\cdot||_A$ denotes the A-norm} in time $${\tilde O}(m\log n \log (1/\epsilon)).$$ The solver utilizes in a standard way a `preconditioning' chain of progressively sparser graphs. To claim the faster running time we make a two-fold improvement in the algorithm for constructing the chain. The new chain exploits previously unknown properties of the graph sparsification algorithm given in [Koutis,Miller,Peng, FOCS 2010], allowing for stronger preconditioning properties. We also present an algorithm of independent interest that constructs nearly-tight low-stretch spanning trees in time $\tilde{O}(m\log{n})$, a factor of $O(\log{n})$ faster than the algorithm in [Abraham,Bartal,Neiman, FOCS 2008]. This speedup directly reflects on the construction time of the preconditioning chain.
verdicts
UNVERDICTED 3representative citing papers
Sparse-HFS computes semi-supervised learning solutions on large graphs with O(n polylog(n)) space and O(m polylog(n)) time via online spectral graph sparsification.
GSQUEAK produces spectrally accurate sparsifiers for graph Laplacians in a single-pass distributed streaming setting.
citing papers explorer
-
Flows in Almost Linear Time via Adaptive Preconditioning
Algorithms achieve almost-linear time for ℓ_p-norm flow and dual regression problems on unit-weighted graphs for a range of p, plus applications to max-flow and total variation.
-
Large-scale semi-supervised learning with online spectral graph sparsification
Sparse-HFS computes semi-supervised learning solutions on large graphs with O(n polylog(n)) space and O(m polylog(n)) time via online spectral graph sparsification.
-
Improved large-scale graph learning through ridge spectral sparsification
GSQUEAK produces spectrally accurate sparsifiers for graph Laplacians in a single-pass distributed streaming setting.