Source-linked AI summary
Approaching optimality for solving SDD systems
Ioannis Koutis, Gary L. Miller, Richard Peng
TL;DR
Efficient algorithms for general sparse linear systems remain limited, while SDD systems support important algorithmic applications. This paper develops an incremental sparsifier and uses repeated sparsification with recursive preconditioned Chebyshev iteration to obtain an iterative SDD solver with expected time ˜O(m log^2 n log(1/ε)).
Problem
General sparse linear systems are difficult to solve efficiently in terms of the number of non-zero entries, motivating faster methods for SDD systems.
Method
The approach constructs an incremental sparsifier by scaling a low-stretch spanning tree, oversampling remaining edges by stretch, and using repeated sparsification to form a chain for recursive preconditioned Chebyshev iteration.
Results
n −1 + m/k edges and ˜O(k log^2 n)-approximation are achieved by the incremental sparsifier, while the resulting SDD solver computes the stated energy-norm approximation in expected time ˜O(m log^2 n log(1/ε)).
Takeaways & Limitations
The solver provides a conceptually simple and possibly practical iterative method whose sparsification quality supports recursive preconditioning for SDD systems.
Takeaways & Limitations
The incremental sparsifier’s condition-number bound contains two log n factors: one from sampling and one from the low-stretch tree’s average stretch.
Abstract
from arXiv · showhide
We present an algorithm that on input of an $n$-vertex $m$-edge weighted graph $G$ and a value $k$, produces an {\em incremental sparsifier} $\hat{G}$ with $n-1 + m/k$ edges, such that the condition number of $G$ with $\hat{G}$ is bounded above by $\tilde{O}(k\log^2 n)$, with probability $1-p$. The algorithm runs in time $$\tilde{O}((m \log{n} + n\log^2{n})\log(1/p)).$$ As a result, we obtain an algorithm that on input of an $n\times n$ symmetric diagonally dominant matrix $A$ with $m$ non-zero entries and a vector $b$, computes a vector ${x}$ satisfying $||{x}-A^{+}b||_A<ε||A^{+}b||_A $, in expected time $$\tilde{O}(m\log^2{n}\log(1/ε)).$$ The solver is based on repeated applications of the incremental sparsifier that produces a chain of graphs which is then used as input to a recursive preconditioned Chebyshev iteration.
1 Introduction
The paper addresses the challenge of making sparse SDD solvers faster and simpler. It presents a conceptually simple iterative solver with nearly-linear runtime, built around incremental graph sparsification.
- Fast sparse linear-system solvers are important in algorithm design, but efficient methods for general sparse systems remain limited.SDD systems have received substantial progress because their matrices satisfy diagonal-dominance structure.
- SDD solvers support applications including eigenvector computation, spectral sparsification, elliptic PDE systems, lossy flows, spanning trees, and vision or graphics optimization.
- The ST-solver iteratively generates approximate solutions converging to the solution of Ax = b.
- O(m log^15 n) is the ST-solver's stated minimum runtime, and its large logarithmic exponent motivates a faster, simpler design.
- ˜O(m log^2 n) is the runtime of the paper's conceptually simple, possibly practical iterative solver.Its main ingredient is a new incremental graph sparsification algorithm.
2 Preliminaries
The preliminaries establish weighted-graph Laplacians, their positive-semidefinite energy norms, and spectral approximation through a matrix partial order. These notions connect graph approximation to condition numbers and iterative convergence.
- Connected weighted graphs with positive edge weights are represented using n vertices and m edges.
- A positive-semidefinite matrix defines an energy norm through the quadratic form x^T Ax.
- A weighted graph Laplacian uses negative edge weights off the diagonal and sums incident edge weights on the diagonal.
- The order A ⪯ B means B − A is positive semidefinite, equivalently x^T Ax ≤ x^T Bx for every vector x.
- If H κ-approximates G, then x^T L_Hx ≤ x^T L_Gx ≤ κx^T L_Hx, giving condition number at most κ and predicting iterative convergence.
3 Prior work on SDD solvers and related graph theoretic problems
Prior work developed combinatorial preconditioning, low-stretch trees, spectral sparsifiers, and ultrasparsifiers as tools for faster SDD solving. These advances progressively improved approximation quality and runtime, while retaining important dependencies on existing solvers.
- SDD systems reduce in linear time to Laplacian systems of weighted graphs through the double-cover construction.
- Vaidya introduced graph-based preconditioners, motivating combinatorial preconditioning for constructing easier-to-solve graph approximations.
- O(sm) approximation follows when non-tree edges have average stretch s over a spanning tree, enabling an O(m^1.31) solver with low-stretch trees.
- O(m log n + n log^2 n) time produces a spanning tree with total stretch ˜O(m log n), and this construction is indispensable to the paper's upper bound.
- The ST-solver combines partitioning, spectral sparsification, and low-stretch trees to produce ultrasparsifiers with n − 1 + (n/k) edges.
- O(n log n)-edge spectral sparsifiers can be sampled using effective resistance, but the fastest known implementation relies on an SDD solver.
4 Our contribution
The paper introduces an incremental sparsifier that avoids high-stretch missing edges and uses it to build a faster SDD solver. It also gives implications for spectral sparsification and ultrasparsification.
- 4 Our contribution: The cycle-versus-line example shows that similar cuts can coexist with condition number O(n) when a missing edge has stretch O(n).
- 4 Our contribution: The algorithm scales a low-stretch spanning tree by k and oversamples remaining edges by stretch, yielding n − 1 + m/k edges and a ˜O(k log^2 n) approximation.
- 4 Our contribution: The incremental sparsifier is sufficient to construct the paper's claimed solver through a chain of preconditioners and recursive preconditioned Chebyshev iteration.
- 4 Our contribution: ˜O(m log^2 n log(1/ε)) expected time computes an ε-accurate solution for an n×n SDD system with m non-zero entries.
- 4.1 Implications for the graph sparsification problem: ˜O(m log^3 n) randomized time brings the Spielman–Srivastava spectral-sparsifier construction to that runtime through the new solver.
- 4.1 Implications for the graph sparsification problem: (k, O(k log^3 n)) ultrasparsifiers result from applying the incremental sparsifier after Spielman–Srivastava sparsification.
5 Sparsification by Oversampling
The section develops an oversampling scheme that replaces exact effective resistances with efficiently computable upper bounds while preserving a spectral approximation guarantee.
- Sampling scheme: The sampling scheme assigns each edge a sampling weight p′_e and samples edges according to normalized probabilities p_e.The procedure constructs a new graph by repeatedly sampling edges and adding sampled edges with adjusted weights.
- Resistance bounds: Exact effective resistances satisfy Σ_e w_eR_e = n − 1, which controls the total sampling mass in the ideal scheme.The paper notes that approximating effective resistances directly appears at least as hard as solving a system.
- Sampling scheme: p′_e ≥ w_eR_e is sufficient for oversampling to produce a spectral sparsifier with high probability.The oversampling theorem assumes these upper bounds for every edge and succeeds with probability at least 1 − ξ.
- Proof framework: The analysis represents the sampled graph through incidence and diagonal weight matrices, reducing the approximation question to a matrix concentration bound.The proof uses a projection matrix Π and a concentration lemma for independent samples.
- Proof framework: ||ΠSΠ − ΠΠ||2 ≤ 1/2 yields the theorem’s spectral approximation guarantee for the sampled graph.The proof applies the projection property and bounds the sample count using the oversampling assumptions.
- Implication: Using inexact resistance upper bounds weakens the bound on the sampling norm and makes sparsifier density depend on m rather than n.The paper states that this weaker bound is nevertheless sufficient for the solver.
6 Incremental Sparsifier
The incremental sparsifier scales a low-stretch spanning tree, then samples non-tree edges using tree-stretch upper bounds to obtain a sparse, well-conditioned approximation.
- Tree construction: A low-stretch spanning tree can be computed in O(m log n + n log^2 n) time with total stretch ˜O(m log n).The tree supplies efficiently computable upper bounds on non-tree effective resistances.
- Core construction: Scaling the tree by κ incurs condition number κ while enabling aggressive sampling of non-tree edges.Scaling reduces the effective resistance along the tree for non-tree edges by a factor of κ.
- Guarantee: With probability at least 1 − ξ, IncrementalSparsify returns the claimed sparsifier in ˜O(m log n + (n log^2 n + m log^3 n/κ) log(1/ξ)) time.The guarantee combines the condition-number and sample-count bounds.
- Core construction: The algorithm sets p′_e = 1 for tree edges and p′_e = stretch_T(e)/κ for non-tree edges.These values are used as oversampling upper bounds after replacing the original tree with its scaled version.
- Sparsity: The resulting graph has n − 1 tree edges plus a sampled non-tree component whose size is controlled by ˜O((m/κ) log n).The sampling analysis bounds the expected and concentrated number of non-tree samples.
7 Solving using Incremental Sparsifiers
The solver repeatedly applies IncrementalSparsify to build a progressively smaller graph chain, then uses recursive preconditioned Chebyshev iteration to solve the original system.
- Chain construction: The preconditioning phase alternates sparsification and GreedyElimination to build C = {A1, B1, A2, …, Ad}.The chain construction is independent of the right-hand side b.
- Chain construction: A κ(n)-good chain requires Ai ⪯ Bi ⪯ κ(ni)Ai at each level.This condition captures the spectral quality needed by the recursive solve phase.
- Solve phase: Recursive preconditioned Chebyshev iteration uses a good chain to compute an approximate solution with error ε.Its expected solve time depends on the chain quality and the target accuracy.
- Solver improvement: Replacing UltraSparsify with IncrementalSparsify produces a faster solver and a better chain for the solve phase.The paper identifies this replacement as the main difference from the Spielman–Teng approach.
- Solver improvement: ˜O(log^4 n)-good chains are constructed with probability at least 1 − p in ˜O((m log n + n log^2 n) log(1/p)) time.Greedy elimination reduces the graph size rapidly, allowing the costs across levels to be summed.
- Final guarantee: ˜O(m log^2 n log(1/ε)) expected time suffices to solve the SDD system to relative A-norm error ε.This is the stated main theorem for an n × n SDD matrix with m non-zero entries.
8 Comments / Extensions
The analysis attributes the incremental sparsifier’s two log n factors to sampling and low-stretch-tree terms, while suggesting diameter-restricted local sparsification as a simpler alternative for some graphs.
- Two log n factors arise from the Rudelson–Vershynin sample bound and the low-stretch tree’s average stretch.
- For some graphs, the low-stretch construction and its associated lower bound might be bypassed by a simpler approach.
- In unweighted graphs, ball growing could concede a 1/log n fraction of edges while keeping the remainder in clusters of diameter O(log^2 n).
- The proposed diameter-restricted local sparsification simplifies low-stretch-tree design within small-diameter clusters and is identified as an implementation direction.
9 Appendix: The Complete Solver
The appendix details a recursive preconditioned Chebyshev solver built from partial Cholesky elimination and a chain of progressively smaller graph systems. It explains how sparsifiers provide preconditioners that can be solved recursively while preserving efficient operations.
- Appendix: The Complete Solver: A partial Cholesky factorization produces a Schur complement A_k; for Laplacians, the reduced matrix remains a Laplacian.
- Appendix: The Complete Solver: GreedyElimination can find degree-1 and degree-2 eliminations and their Laplacian output in linear time, while enabling O(n)-time back-substitution under the stated ordering.
- Appendix: The Complete Solver: Iterative methods avoid fill by generating approximate solutions with matrix-vector multiplications and simple vector-vector operations.
- Appendix: The Complete Solver: Preconditioned Chebyshev iteration applies Chebyshev iteration to B^+Ax = B^+b and accesses the preconditioner through solves with B.
- Appendix: The Complete Solver: After O((λ_max/λ_min) log(1/ε)) Chebyshev iterations, the returned vector satisfies the stated energy-norm error guarantee.
- Appendix: The Complete Solver: An incremental sparsifier B_1 serves as a preconditioner whose degree-1 and degree-2 nodes allow GreedyElimination to reduce it before recursion.
- Appendix: The Complete Solver: The preconditioning chain contains progressively smaller systems A = A_1, B_1, A_2, B_2, ..., A_d and associated factorization operators.
- Appendix: The Complete Solver: The complete solver builds a chain and invokes recursive preconditioned Chebyshev for approximately O~(log^2 n log(1/ε)) iterations.