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

By Daniel A. Spielman, Shang-Hua Teng. 2003

1,026 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities (2014, methodology): “One can employ the recent developments on fast Laplacian solvers to .nd such vectors in near-linear time [Spielman and Teng 2004; Koutis et al.”
Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, background): “e sparsiers of [12, 63, 64, 10] are not linear and do not appear to be mergeable.”
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs (2010, methodology): “This allows us to use the result of Koutis, Miller, and Peng [20], which builds on the work of Spielman and Teng [29] (see also [19, 18]), to approximately solve our linear system in nearly-linear time.”
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs , and its Multicommodity Generalizations (2013, background): “Fast solvers for Laplacian linear systems In their breakthrough paper [30], Spielman and Teng showed how to solve Laplacian systems in nearly-linear time.”
Graph sparsification by effective resistances (2008, methodology): “The tools we use to do this are Spielman and Teng’s nearly-linear time solver [23, 24] and the Johnson-Lindenstrauss Lemma [17, 1].”
Information and Influence Propagation in Social Networks (2013, background): “e theoretical computer science community has developed a number of important techniques for near-linear-time graph algorithm design, including graph sparsification [Benczúr and Karger, 1996] and Laplacian linear system solver [Spielman and Teng, 2004].”
Sketching as a Tool for Numerical Linear Algebra (2014, background): “The bounds on the eigenvalues of a Laplacian are given in [109] (the bound on the maximum eigenvalue follows from the fact that n is the maximum eigenvalue of the Laplacian of the complete graph on n vertices.”
Integro: Leveraging Victim Prediction for Robust Fake Account Detection in OSNs (2015, methodology): “We start with a short overview of our approach, after which we proceed with a detailed description of each system component.”
GAKE: Graph Aware Knowledge Embedding (2016, methodology): “Similar methods are also used in (Spielman and Teng, 2004) and (Perozzi et al.”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, methodology): “Local spectral methods were introduced in [Spielman and Teng 04a]; see also [Andersen et al.”