Approaching Optimality for Solving SDD Linear Systems
From MaRDI portal
Publication:5419043
DOI10.1137/110845914zbMath1310.68274MaRDI 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
iterative solvers; graph sparsification; symmetric diagonally dominant linear systems; combinatorial preconditioning
65F50: Computational methods for sparse matrices
68W40: Analysis of algorithms
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
65F10: Iterative numerical methods for linear systems
65F08: Preconditioners for iterative methods
Related Items
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time, Ranking and Sparsifying a Connection Graph, Unnamed Item, Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank, Unnamed Item, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, Graph Clustering using Effective Resistance, Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems, Unnamed Item, Advances in metric embedding theory, Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving, Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis, 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, A fast algorithm for manifold learning by posing it as a symmetric diagonally dominant linear system, Spectral sparsification in the semi-streaming setting, Engineering a combinatorial Laplacian solver: lessons learned, On graph parameters guaranteeing fast sandpile diffusion, Fitting a graph to one-dimensional data, A Simple Efficient Interior Point Method for Min-Cost Flow, Approximating Spectral Clustering via Sampling: A Review
