Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

Abstract

We present a randomized algorithm that, on input a symmetric, weakly diagonally dominant n-by-n matrix A with m nonzero entries and an n-vector b, produces a y such that $\norm{y - \pinv{A} b}_{A} \leq ε\norm{\pinv{A} b}_{A}$ in expected time $O(m{\log }^{c}n\log (1/\epsilon )),$ for some constant c. By applying this algorithm inside the inverse power method, we compute approximate Fiedler vectors in a similar amount of time. The algorithm applies subgraph preconditioners in a recursive fashion. These preconditioners improve upon the subgraph preconditioners first introduced by Vaidya (1990). For any symmetric, weakly diagonally-dominant matrix A with non-positive off-diagonal entries and $k\ge 1$, we construct in time $O(m{\log }^{c}n)$ a preconditioner B of A with at most $2(n-1)+O((m/k){\log }^{39}n)$ nonzero off-diagonal entries such that the finite generalized condition number ${\kappa }_f(A,B)$ is at most k, for some other constant c. In the special case when the nonzero structure of the matrix is planar the corresponding linear system solver runs in expected time $O(n{\log }^{2}n+n\log n\log \log n\log (1/\epsilon ))$. We hope that our introduction of algorithms of low asymptotic complexity will lead to the development of algorithms that are also fast in practice.

This revised version contains a new section in which we prove that it suffices to carry out the computations with limited precision

References in corpus (1)

• Support-Graph Preconditioners for 2-Dimensional Trusses

Cited by in corpus (29)

• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Approaching optimality for solving SDD systems
• A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning
• A Note on Preconditioning by Low-Stretch Spanning Trees
• Spectral Sparsification of Graphs
• Hamiltonian sparsification and gap-simulations
• Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs
• Faster generation of random spanning trees
• An Efficient Algorithm for Unweighted Spectral Graph Sparsification
• A Fast Distributed Solver for Symmetric Diagonally Dominant Linear Equations
• 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 Effective Resistances
• Scalable Constrained Clustering: A Generalized Spectral Method
• Nearly Maximum Flows in Nearly Linear Time
• Inverses of symmetric, diagonally dominant positive matrices and applications
• Twice-Ramanujan Sparsifiers
• Finite Volume Spaces and Sparsification
• Cohomologous Harmonic Cochains
• Generalized Preconditioning and Network Flow Problems
• Preconditioning in Expectation
• Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver
• Near-Optimal Distributed Maximum Flow
• A General Framework for Graph Sparsification
• A Linear-time Algorithm for Sparsification of Unweighted Graphs
• Finding Sparse Cuts Locally Using Evolving Sets
• Faster spectral sparsification and numerical algorithms for SDD matrices
• Subgraph Sparsification and Nearly Optimal Ultrasparsifiers
• Near Linear-Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs