{"ID":2869812,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.13891","arxiv_id":"2509.13891","title":"On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time","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.","short_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 dominan...","url_abs":"https://arxiv.org/abs/2509.13891","url_pdf":"https://arxiv.org/pdf/2509.13891v2","authors":"[\"Tsz Chiu Kwok\",\"Zhewei Wei\",\"Mingji Yang\"]","published":"2025-09-17T10:36:52Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}