Approaching optimality for solving SDD systems

Abstract

We present an algorithm that on input of an $n$-vertex $m$-edge weighted graph $G$ and a value $k$, produces an {\em incremental sparsifier} $\hat{G}$ with $n-1+m/k$ edges, such that the condition number of $G$ with $\hat{G}$ is bounded above by $\tilde{O}(k{\log }^{2}n)$, with probability $1-p$. The algorithm runs in time $$\tilde{O}((m\log n+n{\log }^{2}n)\log (1/p)).$$ As a result, we obtain an algorithm that on input of an $n\times n$ symmetric diagonally dominant matrix $A$ with $m$ non-zero entries and a vector $b$, computes a vector $x$ satisfying $||x-A^{+}b|{|}_A<\epsilon ||A^{+}b|{|}_A$, in expected time $$\tilde{O}(m{\log }^{2}n\log (1/\epsilon )).$$ The solver is based on repeated applications of the incremental sparsifier that produces a chain of graphs which is then used as input to a recursive preconditioned Chebyshev iteration.

To appear in FOCS 2010

References in corpus (1)

• Nearly Tight Low Stretch Spanning Trees

Cited by in corpus (20)

• A nearly-mlogn time solver for SDD linear systems
• Fast Generation of Random Spanning Trees and the Effective Resistance Metric
• Least Squares Ranking on Graphs
• Solving Linear Programs with Sqrt(rank) Linear System Solves
• Minimum Cost Flows, MDPs, and ${\ell }_1$-Regression in Nearly Linear Time for Dense Instances
• Conditional Hardness of Earth Mover Distance
• Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
• A Fast Distributed Solver for Symmetric Diagonally Dominant Linear Equations
• Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
• Spectral Clustering via the Power Method -- Provably
• Graph Sparsification by Edge-Connectivity and Random Spanning Trees
• Cohomologous Harmonic Cochains
• Distributed SDDM Solvers: Theory & Applications
• Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs
• Faster spectral sparsification and numerical algorithms for SDD matrices
• Faster Approximate Multicommodity Flow Using Quadratically Coupled Flows
• A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
• Simple parallel and distributed algorithms for spectral graph sparsification
• Evaluating the Potential of a Dual Randomized Kaczmarz Solver for Laplacian Linear Systems