A Note on Preconditioning by Low-Stretch Spanning Trees

Daniel A Spielman; Jaeoh Woo

A Note on Preconditioning by Low-Stretch Spanning Trees

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 0903.2816 v1 pith:YCWNWDZ5 submitted 2009-03-16 cs.NA cs.DScs.NA

Daniel A Spielman , Jaeoh Woo This is my paper · ORCID

classification cs.NAcs.DS

keywords linearepsilonlaplacianlow-stretchpreconditionedpreconditioningsolvespanning

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

abstract

Boman and Hendrickson observed that one can solve linear systems in Laplacian matrices in time $\bigO{m^{3/2 + o (1)} \ln (1/\epsilon)}$ by preconditioning with the Laplacian of a low-stretch spanning tree. By examining the distribution of eigenvalues of the preconditioned linear system, we prove that the preconditioned conjugate gradient will actually solve the linear system in time $\softO{m^{4/3} \ln (1/\epsilon)}$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
cs.DS 2025-07 conditional novelty 8.0 of 10

New recursive preconditioning algorithms solve k-well-conditioned linear systems and regressions in Õ(d² + k^ω) time, matching the conditional lower bound and yielding the first nearly-linear-time nuclear norm approximation.

Pith tools