An Efficient Parallel Solver for SDD Linear Systems

Daniel A. Spielman; Richard Peng

An Efficient Parallel Solver for SDD Linear Systems

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1311.3286 v1 pith:JTTHKZEU submitted 2013-11-13 cs.NA cs.DScs.NA

An Efficient Parallel Solver for SDD Linear Systems

Richard Peng , Daniel A. Spielman This is my paper

classification cs.NA cs.DScs.NA

keywords algorithmmatricessystemsequationsinverselinearparallelsolving

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

0 comments

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.

discussion (0)

Forward citations

Cited by 1 Pith paper

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

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.