Approaching Optimality for Solving SDD Linear Systems

DOI10.1137/110845914zbMath1310.68274OpenAlexW2099143789MaRDI QIDQ5419043

Richard Peng, Ioannis Koutis, Gary Lee Miller

Publication date: 4 June 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/110845914

zbMATH Keywords

iterative solversgraph sparsificationsymmetric diagonally dominant linear systemscombinatorial preconditioning

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Analysis of algorithms (68W40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Iterative numerical methods for linear systems (65F10) Preconditioners for iterative methods (65F08)

Related Items (26)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Unnamed Item ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ Spectral sparsification in the semi-streaming setting ⋮ Fitting a graph to one-dimensional data ⋮ A Simple Efficient Interior Point Method for Min-Cost Flow ⋮ Unnamed Item ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Minimum cost flow in the CONGEST model ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Hardness of graph-structured algebraic and symbolic problems ⋮ Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model ⋮ Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique ⋮ Graph Clustering using Effective Resistance ⋮ Approximating Spectral Clustering via Sampling: A Review ⋮ Advances in metric embedding theory ⋮ Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis ⋮ Engineering a combinatorial Laplacian solver: lessons learned ⋮ Ranking and Sparsifying a Connection Graph ⋮ On graph parameters guaranteeing fast sandpile diffusion ⋮ Unnamed Item ⋮ Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank ⋮ Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems ⋮ A fast algorithm for manifold learning by posing it as a symmetric diagonally dominant linear system

This page was built for publication: Approaching Optimality for Solving SDD Linear Systems