A simple, combinatorial algorithm for solving SDD systems in nearly-linear time

DOI10.1145/2488608.2488724zbMath1293.68145arXiv1301.6628OpenAlexW1979505770MaRDI QIDQ5495863

Lorenzo Orecchia, Jonathan A. Kelner, Aaron Sidford, Zeyuan Allen Zhu

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1301.6628

zbMATH Keywords

linear systemLaplacianKaczmarzSDDelectric flow

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (max. 100)

iSIRA: integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big data ⋮ Fitting Laplacian regularized stratified Gaussian models ⋮ Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs ⋮ Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method ⋮ Fitting a graph to one-dimensional data ⋮ A Simple Efficient Interior Point Method for Min-Cost Flow ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ Matrix-Free Convex Optimization Modeling ⋮ Duality and nonlinear graph Laplacians ⋮ Minimum cost flow in the CONGEST model ⋮ Unnamed Item ⋮ 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 ⋮ Network Essence: PageRank Completion and Centrality-Conforming Markov Chains ⋮ Graph Clustering using Effective Resistance ⋮ The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods ⋮ Using Petal-Decompositions to Build a Low Stretch Spanning Tree ⋮ Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis ⋮ Engineering a combinatorial Laplacian solver: lessons learned ⋮ A queueing network-based distributed Laplacian solver ⋮ Amortized Analysis of Asynchronous Price Dynamics ⋮ A Posteriori Error Estimates for Multilevel Methods for Graph Laplacians ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ Local Flow Partitioning for Faster Edge Connectivity ⋮ On a refinement-free Calderón multiplicative preconditioner for the electric field integral equation ⋮ A New Approach to Laplacian Solvers and Flow Problems ⋮ Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank ⋮ Electrical flows over spanning trees ⋮ RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems ⋮ Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems

This page was built for publication: A simple, combinatorial algorithm for solving SDD systems in nearly-linear time