An Efficient Parallel Solver for SDD Linear Systems
Preprint
Abstract
We present the first parallel algorithm for solving systems of linear equations in symmetric, diagonally dominant (SDD) matrices that runs in polylogarithmic time and nearly-linear work. The heart of our algorithm is a construction of a sparse approximate inverse chain for the input matrix: a sequence of sparse matrices whose product approximates its inverse. Whereas other fast algorithms for solving systems of equations in SDD matrices exploit low-stretch spanning trees, our algorithm only requires spectral graph sparsifiers.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear SystemsSIAM Journal on Matrix Analysis and Applications, 2014
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph PartitioningSIAM Journal on Computing, 2013
- Spectral Sparsification in the Semi-streaming SettingTheory of Computing Systems, 2012
- Twice-Ramanujan SparsifiersSIAM Journal on Computing, 2012
- Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processingComputer Vision and Image Understanding, 2011
- Solving Elliptic Finite Element Systems in Near-Linear Time with Support PreconditionersSIAM Journal on Numerical Analysis, 2008
- Component‐based iterative methods for sparse linear systemsConcurrency and Computation: Practice and Experience, 2006
- Random Vectors in the Isotropic PositionJournal of Functional Analysis, 1999
- Efficient approximate solution of sparse linear systemsComputers & Mathematics with Applications, 1998