On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time

Tsz Chiu Kwok, Zhewei Wei, Mingji Yang

TL;DR

This paper extends the frontier of sublinear-time algorithms from symmetric (SDD) to asymmetric diagonally dominant (RDD/CDD) linear systems. By introducing a novel structural measure called the maximum $p$-norm gap, the authors provide a unified algorithmic framework—combining random walks and "local push" methods—to estimate solutions for fundamental graph problems like PageRank and effective resistance with improved complexity bounds.

What Problem Does This Paper Address?

Solving linear systems of the form $Mx = b$ is a foundational task in computer science. While we have "nearly-linear" solvers (running in time proportional to the number of non-zero entries), some applications require sublinear-time solvers. These algorithms don't compute the whole vector $x$; instead, they estimate a specific property, like a single entry or a dot product $t^\top x^*$, by only looking at a tiny fraction of the matrix.

Until now, sublinear solvers were largely restricted to Symmetric Diagonally Dominant (SDD) systems. However, many real-world networks (like the web or directed social graphs) are asymmetric. These are often represented as Row/Column Diagonally Dominant (RDD/CDD) systems. Asymmetric matrices are harder to handle because they lack the nice spectral properties (like eigendecomposition) that researchers usually rely on to prove an algorithm will converge quickly.

Methods

The authors tackle the asymmetry problem through three main contributions:

  1. Mathematical Reformulation: They express the solution $x^*$ using a "lazified" Neumann series. To ensure this series converges for asymmetric matrices, they introduce the maximum $p$-norm gap ($\gamma_{max}$). This is a generalization of the "spectral gap" used for symmetric matrices and serves as the key parameter governing how "well-conditioned" the system is.
  2. Algorithmic Toolkit: They adapt and combine three classic techniques:
  3. Random-walk sampling: Estimating the series by simulating paths on a graph.
  4. Local Push: A deterministic method that iteratively "pushes" residue values to neighbors to refine an estimate.
  5. Bidirectional Method: A hybrid approach that starts a "push" from one end and random walks from the other to meet in the middle, optimizing the trade-off between exploration and accuracy.
  6. Unification: A major highlight is showing that two famous graph algorithms—ForwardPush and BackwardPush—are actually the same algebraic primitive applied to different linear systems.

Datasets

As a theoretical paper focused on algorithmic complexity and proofs, it does not use empirical training datasets. Instead, the authors evaluate their algorithms' performance through rigorous complexity analysis on:

  • General RDD/CDD/RCDD matrices.
  • Directed and Eulerian graphs (where the sum of in-degrees equals the sum of out-degrees).
  • Unweighted undirected graphs (as a special case for comparison with prior SDD solvers).

Key Insights and Ideas

  • The Power of Lazification: By analyzing the operator $\frac{1}{2}(I + D_M^{-1}A_M^\top)$, the authors ensure the Neumann series converges even when the matrix is not symmetric. This "lazy" step is what allows the transition from SDD to RDD.
  • The $p$-norm Gap as a Universal Metric: The authors realized that while a matrix might not look "dominant" in one specific norm (like the $\ell_\infty$ norm), looking at the maximum gap across all $p$-norms provides a robust measure of the system's structural stability.
  • Bridging Local and Global: The paper connects the world of numerical linear algebra (solving $Mx=b$) with the world of local graph algorithms (computing PageRank). This perspective allows them to port hardness results from one field to the other, proving, for example, that a linear dependence on the accuracy parameter ($\epsilon$) is unavoidable.

Key Results

  • Improved Complexity: The authors achieve sublinear bounds for RDD systems that match or beat previous SDD-only results. For instance, their random-walk solver for RDD systems runs in $\tilde{O}(\|t\|_1^2 \gamma^{-3} \epsilon^{-2})$ time.
  • PageRank Breakthrough: They provide a new randomized algorithm for estimating PageRank on Eulerian graphs that improves upon the previous best-known bounds for undirected graphs.
  • Effective Resistance: They derive a suite of bounds for estimating effective resistance (a measure of "distance" in a circuit) using their bidirectional framework, subsuming several recent specialized results.
  • Lower Bounds: They establish an $\Omega(1/\epsilon)$ lower bound for local solvers, confirming that you cannot achieve high accuracy without a certain minimum number of "probes" into the matrix.

Limitations and Future Work

  • The Gap in the Gap: There is still a discrepancy between the upper bounds (which depend on $\gamma^{-3}$) and the lower bounds (which depend on $\gamma^{-2}$). Closing this gap is a primary goal for future research.
  • Directed Spectral Theory: The authors hope the "maximum $p$-norm gap" will become a standard tool in directed spectral graph theory, potentially leading to new insights into the combinatorial properties of directed graphs.
  • Beyond Diagonally Dominant: While this paper masters RDD/CDD systems, the authors suggest exploring whether these sublinear techniques can be extended to even broader classes, such as general Positive Semidefinite (PSD) systems.

Summary updated

Abstract

We initiate a study of solving a row/column diagonally dominant (RDD/CDD) linear system $Mx=b$ in sublinear time, with the goal of estimating $t^{\top}x^*$ for a given vector $t\in R^n$ and a specific solution $x^*$. This setting naturally generalizes the study of sublinear-time solvers for symmetric diagonally dominant (SDD) systems [AKP19] to the asymmetric case. Our first contributions are characterizations of the problem's mathematical structure. We express a solution $x^*$ via a Neumann series, prove its convergence, and upper bound the truncation error on this series through a novel quantity of $M$, termed the maximum $p$-norm gap. This quantity generalizes the spectral gap of symmetric matrices and captures how the structure of $M$ governs the problem's computational difficulty. For systems with bounded maximum $p$-norm gap, we develop a collection of algorithmic results for locally approximating $t^{\top}x^*$ under various scenarios and error measures. We derive these results by adapting the techniques of random-walk sampling, local push, and their bidirectional combination, which have proved powerful for special cases of solving RDD/CDD systems, particularly estimating PageRank and effective resistance on graphs. Our general framework yields deeper insights, extended results, and improved complexity bounds for these problems. Notably, our perspective provides a unified understanding of Forward Push and Backward Push, two fundamental approaches for estimating random-walk probabilities on graphs. Our framework also inherits the hardness results for sublinear-time SDD solvers and local PageRank computation, establishing lower bounds on the maximum $p$-norm gap or the accuracy parameter. We hope that our work opens the door for further study into sublinear solvers, local graph algorithms, and directed spectral graph theory.
BibTeX
@inproceedings{kwok2026solving,
  author = {Tsz Chiu Kwok and Zhewei Wei and Mingji Yang},
  title = {{On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time}},
  booktitle = {ITCS},
  year = {2026},
  doi = {10.4230/lipics.itcs.2026.89},
}

Loading related content...

Figure