Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

Daniel A. Spielman, Shang‐Hua Teng

Type: Preprint

Publication Date: 2004-06-13

Citations: 821

DOI: https://doi.org/10.1145/1007352.1007372

Abstract

We present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where κf (A) is the condition number of the matrix defining the linear system. Our algorithm applies the preconditioned Chebyshev iteration with preconditioners designed using nearly-linear time algorithms for graph sparsification and graph partitioning.

Locations

arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems	2003	Daniel A. Spielman Shang‐Hua Teng
+	Spectral Sparsification of Graphs	2008	Daniel A. Spielman Shang‐Hua Teng
+ PDF Chat	Spectral Sparsification of Graphs	2011	Daniel A. Spielman Shang‐Hua Teng
+ PDF Chat	Spectral sparsification of graphs	2013	Joshua Batson Daniel A. Spielman Nikhil Srivastava Shang‐Hua Teng
+ PDF Chat	Simple parallel and distributed algorithms for spectral graph sparsification	2014	Ioannis Koutis
+	Simple parallel and distributed algorithms for spectral graph sparsification	2014	Ioannis Koutis
+	Simple parallel and distributed algorithms for spectral graph sparsification	2014	Ioannis Koutis
+	Spectral graph sparsification in nearly-linear time leveraging efficient spectral perturbation analysis	2016	Zhuo Feng
+ PDF Chat	Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices	2015	Ioannis Koutis A. Levin Richard Peng
+	Sparsified Cholesky Solvers for SDD linear systems	2015	Yin Tat Lee Richard Peng Daniel A. Spielman
+	A nearly-mlogn time solver for SDD linear systems	2011	Ioannis Koutis Gary L. Miller Richard Peng
+ PDF Chat	Approaching Optimality for Solving SDD Linear Systems	2014	Ioannis Koutis Gary L. Miller Richard Peng
+	Faster spectral sparsification and numerical algorithms for SDD matrices	2012	Ioannis Koutis A. Levin Richard Peng
+ PDF Chat	Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems	2014	Daniel A. Spielman Shang‐Hua Teng
+	Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems	2006	Daniel A. Spielman Shang‐Hua Teng
+	Towards Scalable Spectral Sparsification of Directed Graphs	2019	Ying Zhang Zhiqiang Zhao Zhuo Feng
+	Solving Sparse Linear Systems Faster than Matrix Multiplication	2020	Richard Peng Santosh Vempala
+	SF-GRASS: Solver-Free Graph Spectral Sparsification	2020	Ying Zhang Zhiqiang Zhao Zhuo Feng
+	Sparse approximations, iterative methods, and faster algorithms for matrices and graphs	2018	Michael B. Cohen
+ PDF Chat	A Nearly-m log n Time Solver for SDD Linear Systems	2011	Ioannis Koutis Gary L. Miller Richard Peng

Works That Cite This (482)

Action	Title	Year	Authors
+	Persistent Laplacians: Properties, Algorithms and Implications	2022	Facundo Mémoli Zhengchao Wan Yusu Wang
+ PDF Chat	Sparsification of Binary CSPs	2020	Silvia Butti Stanislav Živný
+ PDF Chat	NFFT Meets Krylov Methods: Fast Matrix-Vector Products for the Graph Laplacian of Fully Connected Networks	2018	Dominik Alfke Daniel Potts Martin Stoll Toni Volkmer
+	A Queueing Network-Based Distributed Laplacian Solver	2021	Iqra Altaf Gillani Amitabha Bagchi
+	Flows in almost linear time via adaptive preconditioning	2019	Rasmus Kyng Richard Peng Sushant Sachdeva Di Wang
+	Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching	2020	S. Cliff Liu Zhao Song Hengjie Zhang
+	Polynomial Time Algorithms for Dual Volume Sampling	2017	Chengtao Li Stefanie Jegelka Suvrit Sra
+ PDF Chat	High-precision Estimation of Random Walks in Small Space	2020	AmirMahdi Ahmadinejad Jonathan A. Kelner Jack Murtagh John Peebles Aaron Sidford Salil Vadhan
+	Efficient $\widetilde{O}(n/\epsilon)$ Spectral Sketches for the Laplacian and its Pseudoinverse	2017	Arun Jambulapati Aaron Sidford
+	A Queueing Network-Based Distributed Laplacian Solver	2020	Iqra Altaf Gillani Amitabha Bagchi

Works Cited by This (7)

Action	Title	Year	Authors
+	Fast Monte-Carlo algorithms for finding low-rank approximations	2002	Alan Frieze Ramachandran Kannan Santosh Vempala
+	The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems	1988	Gene H. Golub Michael L. Overton
+ PDF Chat	Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems	2004	Daniel A. Spielman Shang‐Hua Teng
+	Fast computation of low rank matrix approximations	2001	Dimitris Achlioptas Frank McSherry
+	The eigenvalues of random symmetric matrices	1981	Zoltán Füredi János Komlós
+	Random walks in a convex body and an improved volume algorithm	1993	László Lovász Miklós Simonovits
+	Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$	2003	Daniel A. Spielman Shang‐Hua Teng