Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Published 13 June 2004
Daniel A. Spielman, Shang‐Hua Teng
Citations784
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper presents algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where ε is the condition number of the matrix defining the linear system.
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.
Keywords
Computer ScienceMathematics
Journal of the ACMMulticommodity max-flow min-cut theorems and their use in designing approximation algorithms
813 Citations1999Tom Leighton, Satish Rao
This paper establishes max-flow min-cut theorems for several important classes of multicommodity flow problems and uses the result to design the first polynomial-time (polylog n-times-optimal) approximation algorithms for well-known NP-hard optimization problems.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
784 Citations2004Daniel A. Spielman, Shang‐Hua Teng
This paper presents algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where ε is the condition number of the matrix defining the linear system.
COMBINATORICAThe eigenvalues of random symmetric matrices
673 Citations1981Zoltán Füredi, János Komlós
It is shown that with probability 1-o(1)all eigenvalues belong to the above intervalI if μ=0, while in case μ>0 only the largest eigenvalueλ1 is outsideI, and λ1 asymptotically has a normal distribution with expectation (n−1)μ+v+(σ2/μ) and variance 2σ2 (bounded variance!).
The Chaco user`s guide. Version 1.0
666 Citations1993Bruce Hendrickson, Robert W. Leland
The Chaco software package allows for recursive application of any of several different methods for finding small edge separators in weighted graphs, including inertial, spectral, Kernighan-Lin and multilevel methods in addition to several simpler strategies.
IBM Journal of Research and DevelopmentLower Bounds for the Partitioning of Graphs
662 Citations1973W. E. Donath, Alan J. Hoffman
SIAM Journal on Numerical AnalysisGeneralized Nested Dissection
549 Citations1979Richard J. Lipton, Donald J. Rose +1 more
It is shown that sparse Gaussian elimination is efficient for any class of graphs which have good separator, and conversely that graphs without good separators are not amenable to sparse GaRussian elimination.
Random Structures and AlgorithmsRandom walks in a convex body and an improved volume algorithm
425 Citations1993László Lovász, Miklós Simonovits
A randomized algorithm using O(n7 log’ n) separation calls to approximate the volume of a convex body with a fixed relative error is given and the mixing rate of Markov chains from finite to arbitrary Markov Chains is analyzed.
SIAM Journal on ComputingA Graph-Theoretic Game and Its Application to the <i>k</i>-Server Problem
312 Citations1995Noga Alon, Richard M. Karp +2 more
The main result is that the value of the game on any $n$-vertex graph is bounded above by $\exp(O(\sqrt{\log n \log\log n}))", which has potential application to the design of communication networks.
Approximating <i>s-t</i> minimum cuts in <i>Õ</i>(<i>n</i><sup>2</sup>) time
266 Citations1996András A. Benczúr, David R. Karger
Fast Monte-Carlo algorithms for finding low-rank approximations
180 Citations2002Alan Frieze, Ramachandran Kannan +1 more
This paper develops an algorithm which is qualitatively faster provided the entries of the matrix are sampled according to a natural probability distribution and the algorithm takes time polynomial in k, 1//spl epsiv/, log(1//spl delta/) only, independent of m, n.
Fast computation of low rank matrix approximations
176 Citations2001Dimitris Achlioptas, Frank McSherry
It is proved that the effect of sampling and quantization nearly vanishes when a low rank approximation to A+E, whose entries are independent random variables with zero-mean and bounded variance is computed.
Numerische MathematikThe convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems
101 Citations1988Gene H. Golub, Michael L. Overton
It is suggested that the Chebyshev and Richardson methods, with reasonable parameter choices, may be more effective than the conjugate gradient method in the presence of inexactness.
SIAM Journal on Matrix Analysis and ApplicationsSupport-Graph Preconditioners
96 Citations2006Marshall Bern, John R. Gilbert +3 more
A preconditionsing technique, called support-graph preconditioning, is presented, and it is used to analyze two classes of Preconditioners, modified incomplete Cholesky.
SIAM Journal on Matrix Analysis and ApplicationsSupport Theory for Preconditioning
96 Citations2003Erik G. Boman, Bruce Hendrickson
A new theorem for bounding support numbers (generalized eigenvalues) where the matrices have a known factorization (not necessarily square or triangular) is presented, which generalizes earlier results based on graph theory.
Numerical Linear Algebra with ApplicationsMaximum‐weight‐basis preconditioners
51 Citations2004Erik G. Boman, Doron Chen +2 more
A novel method for constructing preconditioners for diagonally dominant symmetric positive‐definite matrices for diagonal non‐zeros from A and modifying the diagonal elements to maintain a certain row‐sum property is analyzed.
Solving sparse, symmetric, diagonally-dominant linear systems in time O(m/sup 1.31/
45 Citations2004Daniel A. Spielman, Shang‐Hua Teng
A linear-system solver that produces a vector x/spl tilde/ within relative distance /spl epsi/ of the solution to Ax = b in time O(m/sup 1.31/log(n//spl ePSi/)b/sup O(1)/), where b is the log of the ratio of the largest to smallest non-zero entry of A.
Performance evaluation of a new parallel preconditioner
41 Citations2002Keith Gremban, Gary L. Miller +1 more
A new class of preconditioners is developed that is based on the connectivity of the graphs corresponding to the matrices and are well-structured for parallel implementation, and outperform both diagonal scaling and incomplete Cholesky preconditionsers.
Computers & Mathematics with ApplicationsEfficient approximate solution of sparse linear systems
35 Citations1998John H. Reif
Using iterative algorithms, and building on the work of Vaidya and Gremban et al, this work provides the best known sequential work bounds for the solution of a number of major classes of DD sparse linear systems.
Topics in optimization and sparse linear systems
31 Citations1997Anil Joshi
The quality of a new graph-based preconditioner for large sparse Symmetric Positive Definite Diagonally Dominant (SPDDD) linear systems is analyzed.
arXiv (Cornell University)Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$
23 Citations2003Daniel A. Spielman, Shang‐Hua Teng
Solving Symmetric Diagonally-Dominant Systems by Preconditioning
14 Citations2003Bruce M. Maggs, Gary L. Miller +4 more
This paper designs support-tree preconditioners for n × n matrices with m nonzeros that are symmetric and diagonally-dominant with a nonnegative diagonal (SDD matrix) and shows that dilexp(G) is always at most n, hence the bound is at most O(m √ n log n) for any Laplacian (or SDD) matrix.