A Nearly-m log n Time Solver for SDD Linear Systems

DOI10.1109/FOCS.2011.85MaRDI QIDQ5495033zbMATH OpenOpenAlexFDO

Authors Ioannis Koutis, Richard Peng, Gary L. 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

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Graph algorithms (graph-theoretic aspects) (05C85)

Cited in

(32)

• A fast algorithm for manifold learning by posing it as a symmetric diagonally dominant linear system
• An adaptive fast solver for a general class of positive definite matrices via energy decomposition
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Single pass spectral sparsification in dynamic streams
• Constructing linear-sized spectral sparsification in almost-linear time
• Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems
• Minimum cost flow in the CONGEST model
• A general framework for graph sparsification
• Solving graph Laplacian systems through recursive partitioning and two-grid preconditioning
• iSIRA: integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big data
• A new approach to Laplacian solvers and flow problems
• Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
• Network essence: PageRank completion and centrality-conforming Markov chains
• Variational methods for normal integration
• A spectral approach to the shortest path problem
• Using petal-decompositions to build a low stretch spanning tree
• Hardness of graph-structured algebraic and symbolic problems
• On graph parameters guaranteeing fast sandpile diffusion
• Graph Clustering using Effective Resistance
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
• Fitting a graph to one-dimensional data
• Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
• Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• Spanning tree congestion and computation of generalized Győri-Lovász partition
• Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis
• Diffuse scattering on graphs
• Solving local linear systems with boundary conditions using heat kernel pagerank
• Spectral sparsification in the semi-streaming setting
• A queueing network-based distributed Laplacian solver
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs

This page was built for publication: A Nearly-m log n Time Solver for SDD Linear Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495033)