An efficient parallel solver for SDD linear systems
Open Access
- 31 May 2014
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 333-342
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
Funding Information
- Air Force Office of Scientific Research (FA9550-12-1-0175)
- Simons Foundation
- John D. and Catherine T. MacArthur Foundation
- Microsoft Research
This publication has 28 references indexed in Scilit:
- 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
- Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processingComputer Vision and Image Understanding, 2011
- Spectral Sparsification of GraphsSIAM Journal on Computing, 2011
- Solving Elliptic Finite Element Systems in Near-Linear Time with Support PreconditionersSIAM Journal on Numerical Analysis, 2008
- Sampling from large matricesJournal of the ACM, 2007
- Support-Graph PreconditionersSIAM Journal on Matrix Analysis and Applications, 2006
- Support Theory for PreconditioningSIAM Journal on Matrix Analysis and Applications, 2003
- Random Vectors in the Isotropic PositionJournal of Functional Analysis, 1999
- Efficient approximate solution of sparse linear systemsComputers & Mathematics with Applications, 1998