A nearly-mlogn time solver for SDD linear systems

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.

to appear in FOCS11

References in corpus (2)

• Approaching optimality for solving SDD systems
• Nearly Tight Low Stretch Spanning Trees

Cited by in corpus (26)

• Trend Filtering on Graphs
• Non-Convex Matrix Completion Against a Semi-Random Adversary
• iSIRA: Integrated Shift-Invert Residual Arnoldi Method for Graph Laplacian Matrices from Big Data
• Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space
• The Sketching Complexity of Graph Cuts
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
• Single Pass Spectral Sparsification in Dynamic Streams
• Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric $M$-Matrices
• Minor Sparsifiers and the Distributed Laplacian Paradigm
• Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
• Computing the log-determinant of symmetric, diagonally dominant matrices in near-linear time
• Faster Spectral Sparsification in Dynamic Streams
• Deterministic Tree Embeddings with Copies for Algorithms Against Adaptive Adversaries
• Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
• An Efficient Parallel Algorithm for Spectral Sparsification of Laplacian and SDDM Matrix Polynomials
• Scale-free network optimization: foundations and algorithms
• Low Diameter Graph Decompositions by Approximate Distance Computation
• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
• Spectral Sparsification via Bounded-Independence Sampling
• Fully Dynamic Spectral Vertex Sparsifiers and Applications
• Flows in Almost Linear Time via Adaptive Preconditioning
• Computing Circle Packing Representations of Planar Graphs
• Online Spectral Approximation in Random Order Streams
• Finding Consensus in Multi-Agent Networks Using Heat Kernel Pagerank
• Near Linear-Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs
• Algorithms and Hardness for Linear Algebra on Geometric Graphs