Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

By Daniel A. Spielman, Shang-Hua Teng. SIAM Journal on Matrix Analysis and Applications, 2006

471 citations recorded by the source corpus.

We present a randomized algorithm that on input a symmetric, weakly diagonally dominant $n$-by-$n$ matrix $A$ with $m$ nonzero entries and an $n$-vector $b$ produces an ${\tilde{x}} $ such that $\|{\tilde{x}} - A^{\dagger} {b} \|_{A} \leq \epsilon \|A^{\dagger} {b}\|_{A}$ in expected time $O (m \log^{c}n \log (1/\epsilon))$ for some constant $c$. By applying this algorithm inside the inverse power method, we compute approximate Fiedler vectors in a similar amount of time. The algorithm applies subgraph preconditioners in a recursive fashion. These preconditioners improve upon the subgraph preconditioners first introduced by Vaidya in 1990. For any symmetric, weakly diagonally dominant matrix $A$ with nonpositive off-diagonal entries and $k \geq 1$, we construct in time $O (m \log^{c} n)$ a preconditioner $B$ of $A$ with at most $2 (n - 1) + O ((m/k) \log^{39} n)$ nonzero off-diagonal entries such that the finite generalized condition number $\kappa_{f} (A,B)$ is at most $k$, for some other constant $c$. I...

View Paper: https://www.semanticscholar.org/paper/7bdf3f8eb4fa03ceffbf479a8bf787baf4afb872

How researchers see this paper

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

Citations in the corpus

Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “For approaches of a combinatorial flavor, specific to diagonally dominant systems, we refer to the influential work of Spielman and Teng [169].”
Graph Learning From Data Under Laplacian and Structural Constraints (2016, methodology): “Furthermore, DDGLs are utilized in [27]–[29] to develop efficient algorithms for graph partitioning [27], graph sparsification [28] and solving linear systems [29].”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “For approaches of a combinatorial flavour, specific to diagonally dominant systems, we refer to the influential work of Spielman and Teng [33].”
Minimax Rate for Learning From Pairwise Comparisons in the BTL Model (2020, methodology): “We can now directly apply the results of (Spielman & Teng, 2014), which showed that it is possible to solve Eq.”
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs , and its Multicommodity Generalizations (2013, unknown): “…inequalities we have ρ(A) = max x∈R E U −1 WBL † B T U x ∞ x ∞ ≤ max x∈R E UBL † B T U x 2 1 √ |E| x 2 = |E| · UBL † B T U 2 The result follows from the fact in [29] that Π def = UBL † B T U is an orthogonal projection, and therefore Π 2 ≤ 1 and the fact in [31] [12] [14] [11] that T L † = O(|E|).”
Distributed Multitask Reinforcement Learning with Quadratic Convergence (2018, background): “Generalising the work in [29], we recognise that the inverse can be written as: (D0 −A0) ≈ D 1 2 0 O(logm)”
Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, background): ““discrete” nature, most notably theoretical computer science [39]. However, probabilistic ideas are also increasingly and successfully penetrating “continuous” ﬁelds, such as numerical linear algebra [70, 11, 12, 73, 38, 63, 2], optimization [31, 45, 47, 58, 72, 52], control theory [5, 6, 75], machi”
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations (2013, unknown): “Finally we use “greedy elimination” [24] [10] [12], i.”