PaperlayerView exact revision on arXiv

Source-linked AI summary

A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time

Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu

arXiv:1301.6628v1cs.DSmath.NA

TL;DR

The paper addresses how to solve SDD systems in nearly-linear time without the complex machinery used by earlier solvers. It uses a single low-stretch spanning tree, repeated non-recursive updates, and a lightweight data structure. The resulting algorithm is numerically stable and fastest known in the standard unit-cost RAM model.

  • Problem

    The paper seeks a simpler nearly-linear-time method for approximately solving SDD systems and their associated electrical-flow problems.

  • Method

    The solver uses one low-stretch spanning tree, a simple non-recursive update rule, and a lightweight data structure instead of sparsifiers or recursive preconditioning.

  • Results

    The algorithm is numerically stable, avoids additional bit-precision overhead, and is fastest known for SDD systems in the unit-cost RAM model.

  • Takeaways & Limitations

    Its simple, lightweight design is intended to make SDD solvers easier to understand, modify, and potentially adapt to multicore, distributed, and asynchronous settings.

  • Takeaways & Limitations

    The paper does not yet provide empirical evaluation, and cycle updates can require non-sublinear work when tree cycles are long.

Abstract

from arXiv · show

In this paper, we present a simple combinatorial algorithm that solves symmetric diagonally dominant (SDD) linear systems in nearly-linear time. It uses very little of the machinery that previously appeared to be necessary for a such an algorithm. It does not require recursive preconditioning, spectral sparsification, or even the Chebyshev Method or Conjugate Gradient. After constructing a "nice" spanning tree of a graph associated with the linear system, the entire algorithm consists of the repeated application of a simple (non-recursive) update rule, which it implements using a lightweight data structure. The algorithm is numerically stable and can be implemented without the increased bit-precision required by previous solvers. As such, the algorithm has the fastest known running time under the standard unit-cost RAM model. We hope that the simplicity of the algorithm and the insights yielded by its analysis will be useful in both theory and practice.

1 Introduction

SDD systems admit nearly-linear-time approximate solvers with broad applications, but earlier methods relied on elaborate recursive and spectral machinery. This paper presents a simpler spanning-tree-based approach that is numerically stable and fastest known in the unit-cost RAM model.

  • 1 Introduction: SDD systems can be solved approximately in nearly-linear time, unlike general linear systems with best known time O(n^2.373).The solver targets x satisfying an energy-norm error bound, with nearly-linear time defined in terms of the number of nonzeros and accuracy.
  • 1 Introduction: Fast SDD solvers support scientific computing and graph, machine-learning, vision, image-processing, and biological applications.Applications include resistor-network modeling, finite-element simulation, and foundational graph algorithms.
  • 1.1 Previous Nearly Linear Time Algorithms: Earlier nearly-linear solvers used sparsification, low-stretch trees, recursive preconditioning, and iterative methods such as Chebyshev or Conjugate Gradient.Their framework constructs successively sparser preconditioners and applies them recursively.
  • 1.2 Our Results: The paper introduces a simple combinatorial solver requiring one low-stretch spanning tree and a straightforward data structure, without spectral sparsifiers or recursive preconditioning.The algorithm is described by a short update procedure and is intended to make solver internals easier to modify for related problems.
  • 1.2 Our Results: The algorithm is numerically stable, avoids additional bit-precision overhead, and is fastest known for SDD systems in the unit-cost RAM model.It approximately solves both SDD systems and the dual electrical-flow problem.
  • 1.3 Overview of our approach: Repeating the update process a nearly linear number of times suffices to obtain an ε-approximate solution.The approach reduces arbitrary SDD systems to Laplacian systems and interprets these as electrical-flow problems.

2 Preliminaries

The preliminaries reduce SDD solving to Laplacian and electrical-flow problems, then characterize optimality through tree paths, tree cycles, and KPL. A spanning tree’s stretch-related condition number governs cycle-based updates.

  • Graph and matrix definitions: A weighted connected graph uses edge weights as conductances and resistances re = 1/we, with fixed edge orientations and associated incidence, resistance, and Laplacian matrices.Flows are represented on oriented edges, with reversed directions assigned negated values.
  • Electrical flows: Feasible flows satisfy B^T f = χ, while electrical flows are the unique minimum-energy feasible flows for demands summing to zero.The energy is determined by current squared times resistance on each edge.
  • Electrical flows: Electrical-flow computation is dual to solving the Laplacian system Lx = χ, with optimal voltages represented by L†χ.The primal and dual formulations have strong duality and a corresponding duality gap.
  • Tree paths and cycles: For a spanning tree, each off-tree edge defines a unique tree cycle, and these tree cycles form a basis for the graph’s circulation space.KPL optimality is equivalent to zero resistance inner product with every tree-cycle circulation.
  • Tree quality: The tree condition number measures how well off-tree resistances are approximated by their corresponding cycle resistances and controls sampled cycle updates.It is closely related to total stretch through τ(T) = st(T) + m − 2n + 2.
  • Tree quality: A low-stretch spanning tree with total stretch O(m log n log log n) can be computed in O(m log n log log n) time.Low-stretch trees are used by previous nearly-linear SDD solvers and by the solver developed here.

3 A Simple Nearly-Linear Time SDD Solver

SimpleSolver reduces Laplacian solving to approximate electrical-flow computation, then converts the resulting flow into tree-induced voltages. It uses low-stretch spanning trees, repeated cycle updates, and a lightweight implementation to obtain a nearly-linear-time solver.

  • SDD solving is reduced to solving a Laplacian system for a connected graph, without asymptotic runtime loss.
  • Algorithm: SimpleSolver first constructs a low-stretch spanning tree and a feasible tree-supported flow, then repeatedly performs cycle updates.Each update samples an off-tree edge and adjusts flow along its tree cycle.
  • Algorithm: Cycle updates preserve feasibility because they add circulations whose incidence under the tree is zero.
  • Algorithm: The final feasible flow is converted into an approximate Laplacian solution through its tree-induced voltages.The algorithm returns the tree-induced voltages associated with fK.
  • Guarantees: Each iteration takes O(log n) time using a lightweight data structure, while the algorithm’s energy, voltage quality, and initialization satisfy the required bounds.
  • Guarantees: SimpleSolver outputs a feasible flow and runs for O(m log n log log n log(ε^-1n)) iterations with a suitable low-stretch spanning tree.

4 Convergence Rate Analysis

The convergence analysis links the energy reduction from each sampled cycle update to the duality gap between the current flow and its tree-induced voltages. This establishes multiplicative expected progress while preserving feasibility.

  • Convergence Rate Analysis: Each SimpleSolver iteration maintains feasibility by adding a multiple of a circulation, with the multiple chosen to optimize the update.
  • 4.1 Cycle Update Progress: A naive cycle update can require linear time because a low-stretch tree does not bound the number of edges in each tree cycle.Sampling probabilities can further favor off-tree edges whose cycles contain many edges.
  • 4.1 Cycle Update Progress: The optimal update coefficient follows from minimizing the quadratic flow energy along a circulation direction.
  • 4.1 Cycle Update Progress: For a tree cycle, a cycle update decreases energy by the energy associated with the off-tree edge’s resistance and cycle potential drop.
  • 4.2 Distance to Optimality: The duality gap between a feasible flow and its tree-induced voltages upper-bounds the flow’s distance from optimality and can be expressed using cycle potentials.
  • 4.3 Convergence: Each iteration decreases the expected energy difference from the optimal flow by a multiplicative fraction of the duality gap.
  • 4.3 Convergence: The convergence theorem follows by relating the expected progress variable to the duality gap and applying induction.

5 Cycle Update Data Structure

The cycle-update data structure recursively decomposes a static spanning tree around balanced separators, maintaining path quantities that support each update in O(log n) time.

  • Cycle Updates: Each SimpleSolver iteration selects a random off-tree edge and applies an optimal cycle-flow update to the associated tree cycle.The cycle update is represented as flow changes on the off-tree edge and two root-to-vertex tree paths.
  • Data Structure Interface: The data structure stores off-tree flows and supports initialization plus root-path flow updates.The required update operation adds α to every edge on P(s,a).
  • Recursive Decomposition: A tree vertex separator splits the tree into subtrees of at most n/2 + 1 vertices, enabling recursive decomposition.The separator is found by following the largest child subtree until all remaining subtrees have size at most n/2.
  • Recursive Decomposition: For each decomposed subtree, the structure maintains d drop and d ext to represent path potential drop and external flow contributions.These invariants suffice to answer queries and updates recursively.
  • Complexity: The recursive initialization takes O(n log n), while query and update each take O(log n) time.Each recursion reduces subtree size by at least roughly one half.
  • Linear-Algebra View: The recursive structure also has a linear-algebra view using an O(|V|)-dimensional state vector and O(log |V|)-support query and update vectors.Cycle updates can consequently be implemented as a dot product and vector addition over O(log n) entries.

6 Simple Algorithm Running-Time Analysis

The analysis establishes correctness through expected energy decrease and bounds the solver’s total work using a low-stretch spanning tree and logarithmic-time cycle updates.

  • Running Time: The initial tree-supported flow can be computed by depth-first search in O(n) time, while off-tree resistances can be computed in O(m) time using an offline LCA algorithm.The data structure provides an alternative O(m log n) resistance computation.
  • Correctness: Tree-voltage rounding preserves approximate optimality within polynomial factors when converting an approximate electric flow into tree-induced voltages.The rounding result is used in the proof of the solver’s correctness theorem.
  • Correctness: A random cycle update is analyzed through its expected decrease in the flow-energy error.The proof combines this decrease with the optimality of the electrical flow.
  • Running Time: A low-stretch spanning tree with stretch O(m log n log log n) can be constructed in O(m log n log log n) time.The construction gives τ = O(m log n log log n).
  • Running Time: Each cycle update takes O(log n), initialization and initial-flow setup each take O(n log n), and the total iteration count is O(m log n log(nε−1) log log n).Together these bounds yield the claimed total running time.

7 Improved Running Time

The improved solver reduces the error dependence by scaling tree resistances and randomizing the stopping time, then applies these techniques recursively for the best asymptotic running time proved in the paper.

  • Techniques: The improved algorithm changes tree-edge resistances to obtain a better-quality initial feasible flow and changes the stopping criterion for cycle updates.These techniques target the dependence on ε in the running time.
  • Improved Dependence: A two-step variant improves the error dependence to log(ε−1 log n), while recursive application O(log∗n) times achieves O(log ε−1).The latter is described as the best asymptotic running time proven in the paper.
  • ExampleSolver: ExampleSolver combines tree scaling, a warm-start flow, and a uniformly randomized number of cycle updates.It first computes a flow that is O(log n) from optimal in the scaled graph.
  • Tree Scaling: Tree scaling decreases every tree-edge resistance by κ, improving the tree condition number while preserving flow feasibility.The resulting condition number satisfies τ(T′) < τ(T)/κ + m.
  • Randomized Stopping: Randomized stopping time avoids the extra O(log m) running-time factor caused by converting primal energy guarantees into tree-induced voltage guarantees.The stopping count is chosen uniformly from {0, 1, . . . , ⌈τ⌉−1}.
  • FullSolver: FullSolver recursively applies tree scaling log∗(n) times with carefully chosen parameters to achieve the paper’s best asymptotic running time.Its guarantee is stated in Theorem 7.4.

13 end

FullSolver uses a sequence of progressively scaled spanning trees, transferring approximate flows between successive graphs before a final randomized stopping phase produces the output guarantee.

  • Parameter Choice: The scaling parameters begin with κ1 = log n, then satisfy κi = log κi−1 until κc ≤ 2.The number of stages is therefore tied to iterated logarithmic reduction.
  • Scaled Graph Sequence: Each graph G(i) uses the same spanning tree with tree resistances decreased by a product of scaling factors, and G(c+1) equals the original graph G.The scaled tree condition number is bounded by τ(T) divided by the corresponding product, plus m.
  • Approximation Transfer: The flow produced at stage i is expected to be 1-approximate for G(i) and (2κi −1)-approximate for G(i+1).This inductive transfer property connects the guarantees across successive scaled graphs.
  • Final Guarantee: The final stage starts from an expected (2κc −1)-approximate flow and, after randomized stopping, satisfies the error guarantee of Theorem 7.4.The final flow and its tree-induced voltages are the algorithm’s outputs.
  • Running Time: FullSolver retains O(log n) time per cycle update, and its running-time analysis bounds a representative term by O(m log^2 n log log n).The proof concludes with the desired running-time bound.

8 Numerical Stability

The section establishes that SimpleSolver remains convergent and numerically stable under finite-precision arithmetic, using only moderate precision and integral updates.

  • Finite-precision stability: SimpleSolver achieves the same convergence guarantees with finite-precision arithmetic as under exact arithmetic.The stability analysis begins by replacing the exact-arithmetic assumption.
  • Finite-precision stability: O(max(b, log n, log 1/ε)) bits of precision suffice when input resistances and demand coordinates are b-bit integers bounded by N = 2^b.If inputs and ε fit in log n-bit words, the required precision is correspondingly bounded.
  • Integral updates: Rounding each optimal cycle update to the nearest integer preserves at least 3/4 of the exact energy decrease whenever α* ≥ 1.The analysis classifies off-tree edges with α* ≥ 1 as good.
  • Integral updates: The algorithm can run on a RAM machine with word size O(max(b, log n, log 1/ε)) while maintaining integer flow values.The flow values remain bounded by O(poly(N, n, 1/ε)).
  • Scaling factors: Rounding scaling factors to nearby integers preserves the running-time and convergence analyses while keeping graph resistances rational with a common bounded denominator.The denominator is bounded above by ˜O(log n).

9 A Geometric Interpretation via Alternating Projections

The algorithm admits a geometric interpretation as randomized alternating projections onto cycle-consistency hyperplanes. Its convergence follows from resistance-weighted sampling and the low-stretch tree basis.

  • Projection view: SimpleSolver applies randomized Kaczmarz-style projections onto hyperplanes encoding Kirchhoff potential-law conditions.The hyperplanes are indexed by off-tree cycle-basis vectors.
  • Convergence: The tree condition number τ plays the role of the scaled condition number in randomized Kaczmarz convergence.This connects the spanning-tree quality directly to the geometric convergence analysis.
  • Projection view: Each cycle update preserves the demand constraints because it adds a circulation to the current feasible flow.The updated flow therefore remains demand-feasible at every iteration.
  • Convergence: Iterative projections drive the flow arbitrarily close to the intersection of all cycle-consistency hyperplanes, which is the unique electrical flow.The resistance norm supplies the geometric notion of distance.
  • Randomized progress: The central algorithmic challenge is finding a substantially violated basis direction without scanning all off-tree edges.The randomized sampling rule avoids requiring an explicit search over every direction.
  • Randomized progress: Sampling off-tree directions with probability proportional to resistance yields sufficient expected progress because the low-stretch tree basis correlates with every circulation by at least 1/τ.A uniformly sampled arbitrary orthonormal basis could provide a stronger bound, but is not known to be efficiently constructible here.

10 An Operator View: Linearity and Approximating L†

This section recasts SimpleSolver as a composition of linear projection operators and proves that sufficiently many random cycle updates approximate electrical-flow, voltage, and Laplacian-pseudoinverse operators.

  • Linearity: SimpleSolver is linear for a fixed sequence of sampled off-tree edges, with final flows and tree-induced voltages represented by explicit operators.The construction uses cycle projectors, the tree incidence matrix, and the tree Laplacian.
  • Approximation guarantees: The operator proof bounds convergence through a Frobenius-norm potential and uses Markov’s inequality to obtain the high-probability guarantee.The initial potential is Φ0 = n − 1 because ΠG projects onto an (n − 1)-dimensional space.
  • Pseudoinverse approximation: The flow and voltage operators therefore provide approximate representations of the Laplacian pseudoinverse L† and related operators.This is the main operator-level conclusion of the section.
  • Projection operators: Each cycle update is an orthogonal projection after resistance-based scaling, while the unscaled projector is orthogonal in the resistance inner product.This supplies the operator-theoretic interpretation of the update rule.
  • Projection operators: The global projector ΠG maps resistance-scaled flows orthogonally onto the subspace of electrical flows.This projector is also central in spectral graph studies and spectral sparsification.
  • Approximation guarantees: K′ = ⌈τ log n · st(T) · log(1/δp)⌉ random cycle updates produce, with probability at least 1 − p, a δ-approximate electrical-flow operator.The resulting flow energy is at most a factor of (1 + δ) from optimum for every initial demand vector.
  • Approximation guarantees: The corresponding voltage operator yields, with probability at least 1 − p, a δ-approximate solution to L v = χ for any demand vector χ.The guarantee follows from the operator approximation analysis.

11 Solving without Low Stretch Spanning Trees

The low-stretch spanning tree is used both to condition the cycle-space basis and to represent cycles compactly for efficient updates. The section argues that decomposition trees can serve these roles as well.

  • Alternative structures: The spanning tree provides a well-conditioned cycle-space basis and a compact representation supporting efficient querying and updating.These are the two essential functions motivating alternatives to a low-stretch spanning subgraph.
  • Alternative structures: A Bartal-style decomposition tree can satisfy the same goals, although additional steps are needed to establish the basis property and replicate edges equivalently.The construction is not necessarily a subgraph of the original graph.

A Reduction from SDD Systems to Laplacian Systems

The paper gives a direct variant of Gremban’s reduction from an SDD system to a Laplacian system, preserving approximate solutions. It therefore focuses on connected Laplacians, since disconnected components can be solved independently.

  • Direct reduction: The reduction maps an n-dimensional SDD system directly to a Laplacian system and preserves approximate solutions.This replaces the conventional two-step route through an SDDM matrix and an added ground vertex.
  • Matrix construction: An SDD matrix is decomposed into positive and negative off-diagonal parts, a diagonal absolute-value matrix D1, and nonnegative excess diagonal matrix D2.Ap contains positive off-diagonal entries, An contains negative off-diagonal entries, and D2 = A − Ap − An − D1.
  • Solution recovery: From an exact block-system solution, the difference x1 − x2 yields an exact solution to the original system Ax = b.The block system may have multiple exact solutions, but their defined difference solves the original system.
  • Laplacian system: The constructed block system uses mirrored right-hand sides, b and −b, with diagonal blocks D1 + D2/2 + An and off-diagonal blocks −D2/2 − Ap.The resulting block matrix is asserted to be Laplacian.
  • Approximation guarantee: The paper verifies approximate-solution preservation by analyzing an arbitrary ε-approximate solution to the new Laplacian system and its error components.The analysis introduces error terms such as ê1 = x̂2 − x2.
Loading 1301.6628v1…