Source-linked AI summary
A nearly-mlogn time solver for SDD linear systems
Ioannis Koutis, Gary Miller, Richard Peng
TL;DR
The paper improves SDD linear-system solvers by refining sparsification-chain construction and accelerating low-stretch spanning-tree construction. The resulting solver provides an O(log n) speedup, while the new graph sequences may have independent applications.
Problem
SDD solvers support fastest-known algorithms for numerous graph, optimization, numerical, and scientific-computing problems, including applications involving massive graphs.
Method
The solver modifies and analyzes the KMP10a sparsification algorithm, uses a subtler chain construction, and accelerates low-stretch spanning-tree routines through a specialized data structure.
Results
An O(log n) speedup applies to the listed algorithms, while the low-stretch spanning-tree construction addresses the final bottleneck to an O(m log n) algorithm for very sparse systems.
Takeaways & Limitations
Smooth graph sequences provide logarithmic-size chains with constant condition numbers between successive graphs and may support applications beyond this solver.
Takeaways & Limitations
The solver analysis assumes μ_d is smaller than a fixed constant and requires the preconditioning relation G_i ⪯ H_i ⪯ κ_iG_i.
Abstract
from arXiv · showhide
We present an improved algorithm for solving symmetrically diagonally dominant linear systems. On input of an $n\times n$ symmetric diagonally dominant matrix $A$ with $m$ non-zero entries and a vector $b$ such that $A\bar{x} = b$ for some (unknown) vector $\bar{x}$, our algorithm computes a vector $x$ such that $||{x}-\bar{x}||_A < ε||\bar{x}||_A $ {$||\cdot||_A$ denotes the A-norm} in time $${\tilde O}(m\log n \log (1/ε)).$$ The solver utilizes in a standard way a `preconditioning' chain of progressively sparser graphs. To claim the faster running time we make a two-fold improvement in the algorithm for constructing the chain. The new chain exploits previously unknown properties of the graph sparsification algorithm given in [Koutis,Miller,Peng, FOCS 2010], allowing for stronger preconditioning properties. We also present an algorithm of independent interest that constructs nearly-tight low-stretch spanning trees in time $\tilde{O}(m\log{n})$, a factor of $O(\log{n})$ faster than the algorithm in [Abraham,Bartal,Neiman, FOCS 2008]. This speedup directly reflects on the construction time of the preconditioning chain.
1 Introduction
The paper improves SDD linear-system solving to nearly m log n time by redesigning the preconditioning chain and accelerating low-stretch spanning-tree construction. The resulting speedup applies to algorithms that use SDD solvers and is aimed at massive-graph applications.
- SDD solvers support algorithms for spectral graph analysis, sparsification, differential equations, flow, spanning trees, maximum flow, vision, and graphics.
- The previous solver ran in ˜O(m log^2 n log ǫ^-1), while the new solver runs in ˜O(m log n log ǫ^-1).Here m is the number of nonzero entries, n the number of variables, and ǫ the approximation error.
- The solver uses a preconditioning chain of progressively sparser graphs, with sparsification and elimination determining construction cost and iteration quality.
- 1.1 Overview of our techniques: A deeper analysis of the KMP10a sparsification algorithm shows that off-tree total stretch remains essentially invariant through sparsification and contraction.
- 1.1 Overview of our techniques: ˜O(log^2 n) scaling of the initial low-stretch spanning tree produces a spine-heavy graph whose subsequent chain pairs have constant condition number, except the first pair.
- 1.1 Overview of our techniques: O(log n) faster low-stretch spanning-tree construction removes a bottleneck, while the new chain permits irregular rather than uniformly decreasing edge counts.The tree-construction improvement targets the prior ˜O(m log n + n log^2 n) bottleneck.
2 Background and notation
The paper represents SDD systems through weighted graph Laplacians and develops notation for graph ordering, samples, effective resistance, and tree stretch. These concepts describe spectral equivalence and the quality of spanning-tree-based preconditioners.
- An SDD linear system can be reduced to a weighted-graph Laplacian with positive edge weights.
- Graph addition and scaling are defined through addition and scaling of their Laplacian matrices.
- The graph ordering compares Laplacians through quadratic forms, and condition number κ bounds the pair when G ⪯ cH ⪯ κG.
- A graph of samples represents each weighted edge as parallel edges whose weights sum to the original edge weight.
- For an edge, tree stretch is its weight multiplied by the effective resistance of the unique tree path connecting its endpoints.
- Total off-tree stretch aggregates stretch values over edges outside the spanning tree.
3 Incremental Sparsifier
IncrementalSparsify combines a scaled spanning tree with sampled off-tree edges to produce a spectrally useful, smaller graph. Its analysis bounds sampling quality, stretch, failure probability, and implementation time.
- Sampling procedure: The sampler draws q = C_s t log t log(1/ξ) weighted edge copies, with probabilities normalized from frequencies p′_e.Each sampled copy is reweighted so its expected contribution matches the input edge weight.
- Incremental sparsification: Scaling tree edges by κ reduces off-tree stretches by κ but incurs condition number κ between the original and scaled graphs.The scaled graph is G′ = G + (κ − 1)T, replacing the tree by T′ = κT.
- Incremental sparsification: The output H is the union of the spanning-tree copy and sampled off-tree edges, written as H = (V, E_T ∪ L).This modification preserves the tree explicitly while retaining the sampled non-tree edges.
- Quality guarantees: IncrementalSparsify succeeds with probability at least 1 − 2ξ and runs in ˜O((n log n + t̂ log^2 n) log(1/ξ)) time.The implementation computes tree-based effective resistances in O(m) time and accelerates sampling of off-tree edges with interval searches.
- Quality guarantees: The off-tree sample stretch is uniform: each sampled edge has stretch at most 3C_S log t log(1/ξ) relative to the output tree.The proof shows the sampled edge’s stretch is independent of its original weight, and T_H = 3T′.
4 Solving using Incremental Sparsifiers
The solver builds a chain alternating incremental sparsification with greedy elimination, while preserving low-stretch spanning-tree structure. This yields a good preconditioning chain and the paper’s nearly-mlogn SDD solver.
- Preconditioning chain: The preconditioning phase constructs C = {G_1, H_1, G_2, …, G_d}, alternating sparsification and greedy elimination with condition-number bounds κ_i.The chain begins at G_1 = G and is paired with a list of positive conditioner bounds.
- Greedy elimination: GreedyElimination outputs a spanning tree and does not increase total off-tree stretch: |stretch_T̂(Ĝ)| ≤ |stretch_T(G)|.The proof handles degree-1 and degree-2 eliminations while maintaining connectivity and controlling stretch.
- Preconditioning chain: The chain is good when G_i ⪯ H_i ⪯ κ_iG_i, G_i+1 = GreedyElimination(H_i), and the auxiliary edge-count bounds are satisfied.The definition also requires bounded initial edge counts and a final graph whose size is below a fixed constant.
- Solver guarantee: The resulting solver computes an A-norm ε-approximate solution in expected time ˜O(m log n log(1/ε)).The bound follows by combining the good-chain solver reduction with the chain-construction analysis.
- Low-stretch trees: LowStretchTree runs in O(m log n + n log n log log n) time while achieving stretch_T(e) ≤ O(m log n log log^3 n).This improves the construction bottleneck relevant to sparse systems and the preconditioning chain.
- Chain construction: BuildChain produces a good chain with probability at least 1 − p, using κ_1 = ˜O(log^2 n) and constant κ_i = κ_c for i ≥ 2.Its running time is proportional to the running time of LowStretchTree.
5 Speeding Up Low Stretch Spanning Tree Construction
The paper speeds up low-stretch spanning-tree construction by improving the underlying shortest-path data structure and exploiting graphs with few distinct edge lengths. It retains the prior total-stretch bound while reducing construction time.
- A factor of log n speeds up low-stretch spanning-tree construction while retaining O(m log n log log^3 n) total stretch.The improved algorithm builds a tree in O(m log n + n log n log log n) time.
- The algorithm improves Dijkstra-based routines by using a data structure whose Insert and DecreaseKey cost O(1) amortized and whose DeleteMin costs O(log k) amortized.Here k is the number of distinct edge lengths represented by the data structure.
- With k distinct edge lengths, modified Dijkstra computes all distances in O(m + n log k) time.The same speedup supports BallCut and ConeCut routines used inside the spanning-tree construction.
- Rounding edge lengths ensures each HierarchicalStarPartition iteration has O(log n) distinct weights, enabling faster StarPartition calls.The rounded graph preserves a low-stretch tree for the original graph with O(m log n log log^3 n) total stretch.
- On the rounded graph, HierarchicalStarPartition runs in O(m log m + n log m log log m) time.The rounding step itself is dominated by sorting the edge lengths in O(m log m) time.
6 Discussion
The discussion introduces smooth graph sequences as an alternative preconditioning-chain organization and identifies them as potentially useful beyond this solver. These sequences separate sparsification from greedy elimination while maintaining controlled spectral transitions.
- Smooth sequences: A smooth sequence has logarithmic size, starts with a spine-heavy graph, has constant condition number between consecutive graphs, and ends with a tree.It can be built with one IncrementalSparsify round followed by O(log n) rounds of uniform sampling.
- Alternative chain construction: An alternative preconditioning construction first builds the smooth sequence, then applies a less aggressive GreedyElimination procedure to each graph.The modified elimination handles degree-one nodes normally and restricts degree-two elimination to nodes whose adjacent edges satisfy the stated low-stretch condition.
- Broader relevance: The authors identify smooth graph sequences as a notion of independent interest that may support other applications.