pith. sign in

arxiv: 1311.3286 · v1 · pith:JTTHKZEUnew · submitted 2013-11-13 · 💻 cs.NA · cs.DS

An Efficient Parallel Solver for SDD Linear Systems

Richard Peng , Daniel A. Spielman This is my paper
classification 💻 cs.NA cs.DS
keywords algorithmmatricessystemsequationsinverselinearparallelsolving
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Flows in Almost Linear Time via Adaptive Preconditioning

    cs.DS 2019-06 unverdicted novelty 7.0

    Algorithms achieve almost-linear time for ℓ_p-norm flow and dual regression problems on unit-weighted graphs for a range of p, plus applications to max-flow and total variation.