Talks
Fall 2014
An Efficient Parallel Solver for SDD Linear Systems
Friday, October 31st, 2014, 2:30 pm–3:15 pm
Location:
Calvin Lab Auditorium
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 and resemble W-cycles in the Multigrid method, our algorithm only requires spectral graph sparsifiers and is analogous to V-cycles.
Joint work with Dan Spielman.
Attachment | Size |
---|---|
An Efficient Parallel Solver for SDD Linear Systems (slides) | 3.76 MB |