Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
From MaRDI portal
Publication:2936576
DOI10.1137/090771430zbMath1311.65031arXivcs/0607105OpenAlexW1916091028WikidataQ56386820 ScholiaQ56386820MaRDI QIDQ2936576
Daniel A. Spielman, Shang-Hua Teng
Publication date: 17 December 2014
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0607105
preconditioningrandomized algorithmsupport theorymultilevel algorithmLaplacian matriceslinear equation solverssymmetric weakly diagonally dominant matrices
Probabilistic methods, stochastic differential equations (65C99) Preconditioners for iterative methods (65F08)
Related Items (53)
Self-corrective iterations (SCI) for generalized diagonally dominant matrices ⋮ Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Spectral concentration and greedy \(k\)-clustering ⋮ iSIRA: integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big data ⋮ Graphs, Vectors, and Matrices ⋮ Unnamed Item ⋮ A tractable latent variable model for nonlinear dimensionality reduction ⋮ Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs ⋮ Fitting a graph to one-dimensional data ⋮ Unnamed Item ⋮ Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ Tropical Feynman integration in the Minkowski regime ⋮ Tropical Monte Carlo quadrature for Feynman integrals ⋮ The resistance perturbation distance: a metric for the analysis of dynamic networks ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantifying the structural stability of simplicial homology ⋮ Network Essence: PageRank Completion and Centrality-Conforming Markov Chains ⋮ Cover times, blanket times, and majorizing measures ⋮ Hardness Results for Structured Linear Systems ⋮ Determinant-Preserving Sparsification of SDDM Matrices ⋮ A generalized Cheeger inequality ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Band-restricted diagonally dominant matrices: computational complexity and application ⋮ Graph Clustering using Effective Resistance ⋮ Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs ⋮ Polynomial-time algorithms for submodular Laplacian systems ⋮ An Adaptive Fast Solver for a General Class of Positive Definite Matrices Via Energy Decomposition ⋮ A filter in constructing the preconditioner for solving linear equation systems of radiation diffusion problems ⋮ Unnamed Item ⋮ Space Hardness of Solving Structured Linear Systems. ⋮ Ranking and Sparsifying a Connection Graph ⋮ On graph parameters guaranteeing fast sandpile diffusion ⋮ A spectral approach to the shortest path problem ⋮ Unnamed Item ⋮ On fast computation of directed graph Laplacian pseudo-inverse ⋮ A Class of Symmetric Factored Approximate Inverses and Hybrid Two-Level Solver ⋮ Unnamed Item ⋮ A first hitting time approach to finding effective spreaders in a network ⋮ Toward a spectral theory of cellular sheaves ⋮ Coordinate Difference Matrices ⋮ On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices ⋮ Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations ⋮ A New Approach to Laplacian Solvers and Flow Problems ⋮ Synchronization of Kuramoto Oscillators: Inverse Taylor Expansions ⋮ Near-Optimal Distributed Maximum Flow ⋮ On the de-randomization of space-bounded approximate counting problems ⋮ RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems ⋮ Resistance distances in Cayley graphs on symmetric groups ⋮ A fast algorithm for manifold learning by posing it as a symmetric diagonally dominant linear system
Uses Software
This page was built for publication: Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
