A Nearly-m log n Time Solver for SDD Linear Systems
From MaRDI portal
Publication:5495033
DOI10.1109/FOCS.2011.85zbMath1292.05249OpenAlexW2102560346MaRDI QIDQ5495033
Ioannis Koutis, Richard Peng, Gary Lee Miller
Publication date: 30 July 2014
Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/focs.2011.85
Computational methods for sparse matrices (65F50) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Direct numerical methods for linear systems and matrix inversion (65F05)
Related Items (33)
iSIRA: integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big data ⋮ Variational methods for normal integration ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Spectral sparsification in the semi-streaming setting ⋮ Fitting a graph to one-dimensional data ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Solving Graph Laplacian Systems Through Recursive Partitioning and Two-Grid Preconditioning ⋮ 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 ⋮ Network Essence: PageRank Completion and Centrality-Conforming Markov Chains ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Graph Clustering using Effective Resistance ⋮ Using Petal-Decompositions to Build a Low Stretch Spanning Tree ⋮ Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs ⋮ Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis ⋮ Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition ⋮ A queueing network-based distributed Laplacian solver ⋮ An Adaptive Fast Solver for a General Class of Positive Definite Matrices Via Energy Decomposition ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ On graph parameters guaranteeing fast sandpile diffusion ⋮ A spectral approach to the shortest path problem ⋮ Diffuse scattering on graphs ⋮ A General Framework for Graph Sparsification ⋮ A New Approach to Laplacian Solvers and Flow Problems ⋮ Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank ⋮ RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems ⋮ 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: A Nearly-m log n Time Solver for SDD Linear Systems