On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time

Tsz Chiu Kwok, Zhewei Wei, Mingji Yang

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 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.

Introduction

Solving linear systems of the form $Mx = b$ is a cornerstone of computational science. While nearly-linear time solvers—those running in time proportional to the number of non-zero entries—have seen significant advancement, certain modern applications involving massive datasets require even greater efficiency. In scenarios where only a specific property of the solution is needed, such as a single entry or a dot product $t^\top x^*$, sublinear-time solvers become essential. These algorithms estimate the desired value by probing only a small fraction of the matrix $M$.

Historically, sublinear solvers have been largely restricted to Symmetric Diagonally Dominant (SDD) systems. However, many real-world networks, including the web and directed social graphs, are inherently asymmetric. These are typically represented as Row/Column Diagonally Dominant (RDD/CDD) systems. Asymmetric matrices present a unique challenge: they lack the convenient spectral properties, such as eigendecomposition, that researchers rely on to guarantee algorithmic convergence. This paper bridges that gap, extending sublinear techniques to the asymmetric domain.

Mathematical Framework: The Maximum $p$-norm Gap

To address the challenges of asymmetry, the authors introduce a novel structural measure: the maximum $p$-norm gap ($\gamma_{max}$). In symmetric systems, the "spectral gap" determines the rate of convergence for iterative solvers. In the asymmetric case, the authors demonstrate that the $p$-norm gap serves as the appropriate generalization.

The core of their approach involves expressing the solution $x^*$ through a "lazified" Neumann series. By analyzing the operator $\frac{1}{2}(I + D_M^{-1}A_M^\top)$, the authors ensure convergence even when the matrix is not symmetric. The maximum $p$-norm gap captures the system's structural stability across all $p$-norms, providing a robust metric for the problem's computational difficulty.

Algorithmic Toolkit

The paper develops a unified framework by adapting and combining three fundamental techniques:

  1. Random-Walk Sampling: This stochastic approach estimates the Neumann series by simulating paths on a graph representation of the matrix.
  2. Local Push: A deterministic method that iteratively "pushes" residual values to neighboring nodes to refine the solution estimate locally.
  3. Bidirectional Method: A hybrid approach that combines the strengths of both. By initiating a "push" from one end and random walks from the other, the algorithm optimizes the trade-off between exploration and accuracy, meeting in the middle to reduce total complexity.

One of the paper's most significant conceptual contributions is the unification of ForwardPush and BackwardPush. The authors demonstrate that these two widely used graph algorithms are actually the same algebraic primitive applied to different linear systems, providing a clearer theoretical foundation for random-walk probability estimation.

Key Results and Applications

The proposed framework leads to several breakthroughs in algorithmic complexity and graph theory:

  • Improved Complexity Bounds: The authors achieve sublinear bounds for RDD systems that match or exceed previous results for the simpler SDD case. Their random-walk solver for RDD systems, for instance, runs in $\tilde{O}(\|t\|_1^2 \gamma^{-3} \epsilon^{-2})$ time.
  • PageRank on Eulerian Graphs: The paper provides a new randomized algorithm for estimating PageRank on Eulerian graphs (where in-degrees equal out-degrees), improving upon existing bounds for undirected graphs.
  • Effective Resistance: Using the bidirectional framework, the authors derive a suite of bounds for estimating effective resistance—a measure of distance in circuits—subsuming several specialized recent results.
  • Lower Bounds: The research establishes an $\Omega(1/\epsilon)$ lower bound for local solvers. This confirms that high accuracy cannot be achieved without a minimum number of matrix probes, effectively setting a floor for future algorithmic improvements.

Conclusion and Future Directions

This work establishes a rigorous foundation for solving asymmetric diagonally dominant systems in sublinear time. While it narrows the gap between symmetric and asymmetric solvers, a discrepancy remains between the upper bounds (dependent on $\gamma^{-3}$) and lower bounds (dependent on $\gamma^{-2}$). Closing this gap remains a primary objective for future research.

Beyond complexity improvements, the authors suggest that the "maximum $p$-norm gap" could become a standard tool in directed spectral graph theory. Future work may also explore extending these sublinear techniques to broader classes of matrices, such as general Positive Semidefinite (PSD) systems, further expanding the reach of local numerical linear algebra.

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},
}
Figure