A Note on Preconditioning by Low-Stretch Spanning Trees

Abstract

Boman and Hendrickson observed that one can solve linear systems in Laplacian matrices in time $\bigO{m^{3/2 + o (1)} \ln (1/ε)}$ 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/ε)}$.

References in corpus (1)

• Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

Cited by in corpus (7)

• Non-Bayesian Estimation Framework for Signal Recovery on Graphs
• Nearly-Linear Time Spectral Graph Reduction for Scalable Graph Partitioning and Data Visualization
• Dynamic Graph Algorithms and Graph Sparsification: New Techniques and Connections
• Preconditioning in Expectation
• Faster Subset Selection for Matrices and Applications
• GRASS: Graph Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis
• Faster spectral sparsification and numerical algorithms for SDD matrices