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
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
