Source-linked AI summary
An Efficient Parallel Solver for SDD Linear Systems
Richard Peng, Daniel A. Spielman
TL;DR
Solving SDD linear systems is important across graph and numerical applications, but prior parallel methods did not combine nearly-linear work with polylogarithmic depth. The paper constructs sparse approximate inverse chains using spectral sparsifiers, yielding an SDDM solver with nearly-linear work and polylogarithmic depth.
Problem
The paper addresses efficient parallel solution of SDD linear systems, a problem used in elliptic PDEs, maximum flows, semi-supervised learning, and other algorithms.
Method
The algorithm constructs a sparse approximate inverse chain from spectral sparsifiers, replacing the need for low-stretch spanning trees.
Results
Theorem 1.2 provides an SDDM solver with nearly-linear work and polylogarithmic depth, with work O((m + n log^c n log^3 κ) log 1/ε) and depth O(log n log κ log 1/ε).
Takeaways & Limitations
Sparse approximate inverse chains can support parallel SDDM solving using spectral sparsifiers and without low-stretch spanning trees.
Takeaways & Limitations
The overview notes that dense recursive matrices would require substantial work, so the method must sparsify them; the chain definition also requires a bounded cumulative approximation error.
Abstract
from arXiv · showhide
We present the first parallel algorithm for solving systems of linear equations in symmetric, diagonally dominant (SDD) matrices that runs in polylogarithmic time and nearly-linear work. The heart of our algorithm is a construction of a sparse approximate inverse chain for the input matrix: a sequence of sparse matrices whose product approximates its inverse. Whereas other fast algorithms for solving systems of equations in SDD matrices exploit low-stretch spanning trees, our algorithm only requires spectral graph sparsifiers.
1 Introduction
The paper develops a parallel SDD solver based on sparse approximate inverse chains rather than low-stretch spanning trees, achieving nearly-linear work and polylogarithmic depth.
- Motivation: Solving SDD and graph-Laplacian systems supports applications including elliptic PDEs, maximum flows, and semi-supervised learning.The paper also notes that these systems serve as primitives in many other algorithms.
- Method: The solver replaces low-stretch spanning trees with spectral sparsifiers to construct a sequence of sparse matrices whose product approximates the inverse.Applying each chain matrix twice makes the resulting solver symmetric.
- Contributions: Theorem 1.1 establishes a polynomial-time sparse approximate inverse chain with work O((m + n log^3 κ) log 1/ε) and depth O(log n log κ log 1/ε).This is the stronger existence result underlying the solver guarantees.
- Contributions: Theorem 1.2 gives nearly-linear-work, polylogarithmic-depth construction and solution guarantees for SDDM systems with condition number at most κ.The solver succeeds with probability at least 1/2, using work O((m + n log^c n log^3 κ) log 1/ε) and depth O(log n log κ log 1/ε).
2 Background and Notation
The background introduces SDD-related matrix classes, spectral approximation notation, and condition numbers as the main accuracy and runtime parameters.
- Matrix classes: SDD systems reduce to Laplacian or SDDM systems, while these reductions approximately preserve condition numbers.Laplacians have zero row sums and non-positive off-diagonal entries; SDDM matrices are positive definite SDD matrices with non-positive off-diagonal entries.
- Matrix classes: Weak diagonal dominance permits diagonal entries to equal twice the sum of the absolute off-diagonal entries in their row.Strict diagonal dominance instead requires each diagonal entry to be strictly larger.
- Condition number: The condition number is the ratio of the largest to smallest eigenvalue, or to the second-smallest for Laplacians.The algorithms' running times depend logarithmically on this quantity.
- Approximation: Positive-definite ordering defines matrix approximation through relations such as X ≈_ε Y, whose errors compose across sums, products, inverses, and congruence transformations.These closure properties support the approximate inverse-chain analysis.
3 Overview
The overview derives a recursive solver for SDDM matrices and makes it efficient by sparsifying each recursive matrix, producing an inverse chain with logarithmic depth in the condition number.
- Recursive reduction: The recursive identity reduces solving in D − A to solving in D − AD^-1A, another SDDM matrix, and repeated application produces the chain.The symmetric form is needed because products of sparse approximations need not approximate the product unless applied symmetrically.
- Chain construction: Dense recursive matrices would make direct multiplication expensive, so the algorithm sparsifies them into sparse SDDM matrices at each level.Spectral sparsifiers provide the sparse approximations used to continue the recursion.
- Solver: The solver applies each chain level forward and backward, with work proportional to total chain nonzeros and depth proportional to d log n.The symmetric forward-backward application is the practical Solve procedure.
- Chain construction: Using d = O(log κ) levels and best-known sparsifiers yields chains with O(n log^3 κ) total nonzeros.Efficiently constructible sparsifiers add an O(log^c n) factor, while preserving polylogarithmic depth.
4 Approximate Inverse Chains
Approximate inverse chains let a solver recursively approximate an SDDM inverse, then refine the resulting constant-factor solution to arbitrary precision with preconditioned Richardson iteration.
- Chain definition: The chain is defined through diagonal matrices D_i, nonnegative symmetric matrices A_i, and recursively related SDDM matrices M_i.The construction maintains approximate relationships between successive matrices so that replacing an exact Schur-complement-like term with M_{i+1} remains accurate.
- Solver construction: Preconditioned Richardson iteration requires O(log(1/ǫ)) iterations, each using one multiplication by the system matrix and one by the preconditioner.
- Solver complexity: Given chain matrices with total size m_i, Solve runs in O(d log n log(1/ǫ)) depth and O((Σ_i m_i) log(1/ǫ)) work.
- Solver complexity: Each recursive solver level performs two matrix-vector products per chain matrix, while sparse matrix-vector multiplication determines the work and depth bounds.
5 Existence of Sparse Approximate Inverse Chains
The paper constructs short sparse approximate inverse chains for SDDM matrices by repeatedly preserving SDDM structure, controlling spectral contraction, and applying spectral sparsification.
- Spectral control: Spectral contraction bounds the eigenvalues of D^-1AD^-1A by the squared upper bound on the eigenvalues of D^-1A.
- Chain termination: The final matrix can be approximated by its diagonal after a logarithmic number of levels in the condition number.
- Preserving structure: Each recursive step preserves the SDDM property: if M = D − A, then D − AD^-1A is SDDM and AD^-1A is nonnegative.
- Sparsification: Spectral sparsifiers provide sparse approximations with O(n/ǫ^2) nonzero entries, which are used to sparsify the recursive matrices.
- Chain existence: An n-dimensional SDDM matrix with condition number at most κ has an approximate inverse chain of depth O(log κ) and total size O(n log^3 κ).
- Consequence: Combining the chain construction with the solver theorem yields the paper’s nearly-linear-work, polylogarithmic-depth result.
6 Efficient Parallel Construction
The section develops a parallel sparsification procedure that avoids explicitly constructing dense matrices, then uses the resulting sparsifiers to build sparse approximate inverse chains with nearly-linear work and polylogarithmic depth.
- Parallel spectral sparsification: Theorem 6.1 provides spectral sparsifiers with O(m log^c1 n) work and O(log^c2 n) depth, while retaining approximation quality with probability at least 1 − 1/n^2.The sparsifier has O(n log^c n/ε^2) entries.
- Sparse approximation: The construction approximates D − AD^-1A without forming it densely by decomposing its off-diagonal entries into weighted cliques and sparsifying those cliques individually.A general-purpose sparsification routine then reduces the result to O(n log^c n/ε^2) nonzero entries.
- Sparse approximation: Effective-resistance sampling sparsifies each weighted clique, using O(n log n/ε^2) sampled edges to obtain a spectral approximation with high probability.The edge-sampling distribution is proportional to edge weight times effective resistance.
- Sparse approximation: Corollary 6.4 produces bD and bA with at most O(m log n/ε^2) nonzeros, satisfying bD − bA ≈_ε D − AD^-1A and bD ≈_ε D, in O(m log^2 n/ε^2) time.The procedure succeeds with probability at least 1 − 1/n.
- Approximate inverse chains: Theorem 6.5 constructs an approximate inverse chain of depth O(log κ) with O(n log^c n log^3 κ) total nonzeros and nearly-linear work with polylogarithmic depth.The construction succeeds with probability at least 1/2.
A The Condition Number of a Submatrix
This appendix relates a Laplacian system to a reduced SDDM system by deleting one row and column, then bounds the reduced matrix's condition number using the Laplacian's finite condition number.
- Reduction to a submatrix: Deleting the first row and column of a connected graph Laplacian produces an SDDM matrix whose smallest eigenvalue is at least λ2(L)/n.The proof orthogonalizes the vector against the all-ones nullspace vector.
- Reduction to a submatrix: The reduced system can be solved with the first coordinate fixed to zero, after which the solution is orthogonalized against the Laplacian's all-ones nullspace.This establishes a reduction from solving Lx = b to solving a system in the principal submatrix.
- Condition-number bound: The condition number of the reduced matrix, and of every principal submatrix, is at most n times the Laplacian's finite condition number.The bound follows from eigenvalue interlacing and the lower-eigenvalue estimate.
B Proof of Lemma 5.2
The proof bounds eigenvalues of related normalized matrices through spectral approximation and auxiliary matrix inequalities, establishing the needed contraction estimates for Lemma 5.2.
- Spectral comparison: Proposition B.2 transfers spectral approximations between positive diagonal and nonnegative symmetric matrix pairs to bounds on the eigenvalues of their normalized combinations.Its hypotheses compare eD and bD, as well as eD − eA and bD − bA.
- Eigenvalue bounds: The proof obtains a lower eigenvalue bound of at least μ exp(−ε), followed by a related bound of at least μ exp(−2ε).These estimates arise through successive applications of the auxiliary facts and Proposition B.1.