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




Related Items (33)

iSIRA: integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big dataVariational methods for normal integrationConstructing Linear-Sized Spectral Sparsification in Almost-Linear TimePolynomial fixed-parameter algorithms: a case study for longest path on interval graphsSpectral sparsification in the semi-streaming settingFitting a graph to one-dimensional dataDerandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic SpaceSolving Graph Laplacian Systems Through Recursive Partitioning and Two-Grid PreconditioningGraph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle DecompositionsMinimum cost flow in the CONGEST modelDecentralized Low-Stretch Trees via Low Diameter Graph DecompositionsHardness of graph-structured algebraic and symbolic problemsBrief Announcement: Minimum Cost Maximum Flow in the CONGEST ModelBrief Announcement: The Laplacian Paradigm in Deterministic Congested CliqueNetwork Essence: PageRank Completion and Centrality-Conforming Markov ChainsSingle Pass Spectral Sparsification in Dynamic StreamsGraph Clustering using Effective ResistanceUsing Petal-Decompositions to Build a Low Stretch Spanning TreeNearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphsApproximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network AnalysisSpanning Tree Congestion and Computation of Generalized Györi-Lovász PartitionA queueing network-based distributed Laplacian solverAn Adaptive Fast Solver for a General Class of Positive Definite Matrices Via Energy DecompositionMulti-way spectral partitioning and higher-order cheeger inequalitiesOn graph parameters guaranteeing fast sandpile diffusionA spectral approach to the shortest path problemDiffuse scattering on graphsA General Framework for Graph SparsificationA New Approach to Laplacian Solvers and Flow ProblemsSolving Local Linear Systems with Boundary Conditions Using Heat Kernel PagerankRCHOL: Randomized Cholesky Factorization for Solving SDD Linear SystemsSparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian SystemsA 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