# Sublinear-Time Solvers for Asymmetric Diagonally Dominant Systems
## Overview
Solving large linear systems is a fundamental task in computing, arising in contexts from graph algorithms to AI module coordination. A diagonally dominant matrix is one where each diagonal entry dominates the sum of off-diagonal entries in its row or column. For example, matrix $M=[m_{ij}]$ is row diagonally dominant (RDD) if for each row $i$, $|m_{ii}| \ge \sum_{j\neq i}|m_{ij}|$ (and similarly column diagonally dominant CDD by columns). Such matrices often appear in structured problems like graph Laplacians, network flow constraints, and iterative update systems.
Traditional solvers typically run in at least linear time in the input size. However, sublinear-time solvers aim to compute an approximate solution (or some component of it) without reading the entire input, exploiting special structure. Recent research has extended sublinear solvers beyond the well-studied symmetric case to handle asymmetric diagonally dominant (ADD) systems. This breakthrough means even if the system is not symmetric (e.g. a directed graph or non-reversible network), we can still solve or estimate solutions much faster than naive methods – often in time polylogarithmic in the system size.
## Background: From Symmetric to Asymmetric Systems
For symmetric, diagonally-dominant (SDD) matrices (like Laplacian matrices of undirected graphs), there have been significant advances in efficient solvers. The seminal work of Spielman and Teng (2004) gave a near-linear time algorithm for solving SDD systems, which was a breakthrough for large sparse graphs. In other words, if an $n\times n$ matrix has $m$ nonzero entries, one can approximately solve $Mx=b$ in $O(m \log^{O(1)}n)$ time – almost linear in input size. Subsequent research further improved and simplified these algorithms.
However, near-linear still means reading essentially the whole input. Truly sublinear-time methods go a step further: they return an approximation by accessing only a small fraction of the entries. This is only possible in special cases, typically when we only need part of the solution (e.g. one coordinate or a specific linear functional of the solution) and when the system is well-conditioned. In 2019, Andoni, Krauthgamer, and Pogrow showed that for SDD matrices with good conditioning (e.g. Laplacians of expander graphs), one can approximate a single coordinate $x_u^*$ of the solution in polylogarithmic time (sublinear in $n$). For instance, if the graph is an expander (so it has a large spectral gap / small condition number), the algorithm can estimate $x^*_u$ with additive error $\epsilon ||x^*||_\infty$ in $\mathrm{poly}(\log n)$ time. This was a "local" solver: extremely fast for one part of the solution, under the right conditions. They also proved that without such conditions (e.g. for general positive semidefinite matrices), sublinear time is impossible in the worst case – highlighting that SDD matrices are a special sweet spot where local solvers can exist.
The new frontier is solving asymmetric diagonally dominant systems in sublinear time. In many real-world problems, the system matrix isn't symmetric; for example, directed graphs or one-way influence networks yield non-symmetric matrices. Until recently, sublinear algorithms required symmetry (and often nonnegative diagonals, as in Laplacians) to work. The latest research removes that restriction: we can now handle general diagonally dominant matrices (even with asymmetric or signed off-diagonals) in sublinear time. In short, what was once limited to undirected Laplacian systems has been extended to directed and general ADD systems, vastly broadening the scope of fast solvers.
## Key Concepts and Techniques
### 1. Neumann Series & Generalized Spectral Gap
A core insight is to express the solution of $Mx=b$ in a series form and analyze its convergence. If $M=D+R$ (diagonal $D$ plus off-diagonal $R$) and $D^{-1}R$ has norm < 1, one can write the inverse as a Neumann series:
$$x^* = M^{-1}b = (D+R)^{-1}b = D^{-1}(I+(−D^{-1}R))^{-1}b = D^{-1}\sum_{k \geq 0}(D^{-1}(−R))^k b.$$
This expansion essentially sums walks of increasing length (since $(D^{-1}R)^k$ corresponds to $k$ hops through the off-diagonals). For symmetric matrices, convergence is governed by the spectral radius (eigenvalues) of $D^{-1}R$; a large spectral gap (eigenvalue separation) ensures fast convergence. In the asymmetric case, we lack eigenvalue guarantees, so researchers defined a "maximum $p$-norm gap" as a new measure of matrix expansiveness. This $p$-norm gap generalizes the spectral gap concept for non-symmetric matrices. Intuitively, it quantifies how strongly the diagonal dominates in every direction (not just orthogonal eigen-directions). If the maximum $p$-norm gap is bounded away from 0, the Neumann series converges quickly and the system is well-conditioned for local solving. This concept governs the complexity: a better $p$-norm gap (like a stronger form of diagonal dominance) means easier, faster solving.
### 2. Random-Walk Sampling
Random walks are powerful for exploring large graphs without looking at everything. In the symmetric case, sublinear Laplacian solvers often rely on sampling random walks to estimate influence or potentials between nodes. The new algorithms extend this to asymmetric systems by performing random walk sampling on directed graphs or influence networks. For example, to estimate a particular coordinate of $x^* = M^{-1}b$, one can interpret that coordinate as an influence sum over paths in a directed graph (where $M$ relates to a graph's transition matrix or flow matrix). By sampling many random walks from a node (or from the distribution defined by $t^\top$, the vector whose inner product with $x^*$ we want), the algorithm builds an estimator for $t^\top x^*$ without full matrix inversion. Random walks naturally handle directed edges by following their direction, capturing the asymmetric influence. This technique was crucial in prior special cases like estimating PageRank (random-walk stationary distribution) in a directed web graph – now it's part of the general solver toolkit.
### 3. Local Push (Forward and Backward)
Local push algorithms iteratively "push" residual errors along edges of a graph to approximate solutions like PageRank. In forward push, one starts from a source (like distributing probability mass from a node to its neighbors iteratively, which approximates that node's influence on others). In backward push, one starts from a target and distributes backwards (useful to find which sources contribute to a given node's rank or influence). These were known heuristics for computing personalized PageRank locally. The new framework unifies these as two sides of the same coin. By formalizing the linear system solution as a series of walks, one can choose to propagate errors forward or backward depending on which is more efficient for the query at hand. Forward push corresponds to expanding the Neumann series from the right (simulating influence of $b$ outwards), whereas backward push is like expanding from the test vector $t^\top$ on the left (propagating demands backward to sources). The recent work by Kwok et al. shows that both approaches are instances of their general solver, and it provides a unified understanding of when to use each. This is not only elegant theoretically, but it also yields improved complexity bounds for special cases (they managed to tighten bounds for estimating random-walk probabilities on graphs by optimally mixing forward/backward strategies).
### 4. Bidirectional Combination
In fact, one innovation is to combine forward and backward random-walk approaches. Some problems benefit from a bidirectional search: push from sources and from targets until meeting in the middle. The algorithms leverage this by simultaneously exploring from the $b$ side and the $t$ side, which can drastically reduce the work needed in certain regimes. This hybrid approach was previously hard to analyze, but with the new framework it becomes natural. For example, to estimate an entry of $M^{-1}$ (influence of one node on another), one can perform a forward random walk from the source and a backward random walk from the target and see where they intersect – achieving in sublinear time what a full solve would do in linear time.
### 5. Probabilistic Recurrence Approach
Another line of approach (from Feng, Li, Peng 2025) uses a probabilistic recurrence instead of explicit random walks. They analyze a simple iterative process that approximates the solution vector's coordinates and show it converges quickly on diagonally dominant systems. This avoids some complex graph-theoretic interpretations by working directly with probabilities of influencing neighbors in each step. Their algorithm returns an estimate $\tilde z_u$ of each requested coordinate $z^*_u$ with controllable additive error $\epsilon$ (absolute or relative). Crucially, it only inspects a small portion of $S$ and $b$ – a sublinear sample – to compute $\tilde z_u$. By carefully bounding the variance and bias of this recurrence-based estimator, they guarantee accuracy. They also prove a matching lower bound: any sublinear algorithm must incur at least a linear dependence on certain parameters of $S$. In particular, the complexity of their solver grows linearly with $S_{\max} = \max_i |S_{ii}|$ (the largest diagonal entry). This is intuitive: if diagonal entries are huge, the solver needs proportionally more effort to overcome that scale. They show this linear dependence on $S_{\max}$ is optimal (can't be improved), so their algorithm's scaling is essentially the best possible in terms of that parameter.
## Recent Results and Performance
Two concurrent 2025 works exemplify the progress in this field:
**Kwok, Wei, Yang (2025)** – "On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time." This work establishes the general framework with the maximum $p$-norm gap condition. It proves that if an ADD system has a bounded $p$-norm gap (an assumption analogous to having a well-behaved spectrum in the symmetric case), one can estimate $t^\top x^*$ for a given vector $t$ in sublinear time. The paper adapts and generalizes techniques from the graph domain (random walks, forward/backward push) to arbitrary RDD/CDD matrices. Notably, it unified known algorithms for PageRank and electrical network effective resistance computation under one umbrella. Effective resistance (a measure in undirected graphs related to Laplacian pseudoinverse entries) had fast local estimators; now those are special cases of the broader method. The authors report that their perspective yields deeper insights and improved complexity bounds for these classical problems. They also carry over known hardness results – for instance, they note that if the $p$-norm gap is very small or if extremely high accuracy is required, no sublinear algorithm can exist (these correspond to needing to essentially read the whole input). This mirrors the earlier impossibility results for certain ill-conditioned systems and for exact PageRank.
**Feng, Li, Peng (2025)** – "Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin–Johnsen Model." This work independently tackles the problem with a different technique. It broadens the scope of sublinear solvers to any strictly diagonally dominant matrix ($\delta>0$ in the dominance condition) and even some cases where dominance is weak ($\delta=0$). Importantly, it does not require the matrix to be symmetric or the diagonal entries to be positive, overcoming a limitation of previous sublinear solvers. The authors devise a randomized algorithm based on the probabilistic recurrence idea: treat the solution vector as the fixed point of an iterative random process and approximate it by simulation. They achieve impressive complexity results. For example, in the strictly dominant case, to get an absolute error $\epsilon$, one algorithm runs in time on the order of:
$$O\left(\frac{||b||_\infty^2 S_{\max}}{\delta^3 \epsilon^2} \log \frac{||b||_\infty}{\delta \epsilon}\right),$$
where $S_{\max}$ is the largest diagonal magnitude. This is sublinear in $n$ for many scenarios (it depends on values of $b$ and matrix parameters, but not directly on $n$ except via a logarithm inside $||b||_\infty$). They also prove no algorithm can avoid a linear factor in $S_{\max}$, meaning their algorithm's dependence on matrix scaling is optimal. An interesting application they highlight is to a well-known social network opinion dynamics model (Friedkin–Johnsen model). In that model, people's opinions reach an equilibrium according to a weighted influence matrix $S$ (which is typically diagonally dominant because each person's own stubbornness dominates external influence). Using their solver, one can estimate an individual's steady-state opinion (a coordinate of $S^{-1}b$) much faster than before, even in a large network. They obtained an improved sublinear algorithm for opinion estimation in this model as a direct corollary. This showcases the practical impact: complex social-influence networks (which are directed and weighted) can be analyzed in sublinear time per query, something previously feasible only for undirected or very symmetric cases.
## Applications and Impact
The ability to solve ADD systems in sublinear time isn't just a theoretical win – it opens doors to faster computation in many domains. Here are some key implications and use cases:
**Graph Algorithms (Directed Networks):** Many problems on directed graphs boil down to linear systems. For example, computing PageRank or other random-walk based metrics can be seen as solving $(I - \alpha P^T)x = v$ for a stochastic matrix $P$ (not symmetric in general). With new solvers, one can obtain such metrics locally without iterating over the whole graph, which is crucial for huge web graphs or social networks. Similarly, computing reachability probabilities, influence scores, or flow distributions in directed networks can leverage these techniques. Effective resistance and electrical flows in undirected graphs already benefitted from fast solvers; now their directed analogues can too.
**Distributed Systems and Swarm Verification:** In advanced AI architectures, one might have swarms of agents or neural modules interacting. Ensuring consistency or equilibrium in such a swarm can lead to solving large structured linear systems. For instance, a "ruv-swarm" verification loop might involve agents cross-checking outputs such that each agent's "belief" is adjusted by neighbors' feedback (forming a diagonally dominant update matrix because each agent trusts itself most). A sublinear solver could verify or approximate the swarm's consensus state much faster, by sampling interactions instead of checking every link. This accelerates verification loops that ensure the swarm isn't hallucinating or diverging, by effectively solving the equilibrium equations quickly at each step.
**Neural Network Flow Balancing:** Consider a scenario like Flow-Nexus cost checks or Claude-flow (possibly referring to managing flow of information or gradients in large AI models). These can be abstracted as flows in a network where each node/module must satisfy a balance between incoming and outgoing "flow" (information or resource). The constraints here form a linear system (often diagonally dominant if each module's self-regulation outweighs external inputs). Sublinear algorithms enable checking such flow balance conditions or computing adjustments without a full sweep of the entire network graph. This means global consistency checks or optimizations in a big model can be done by probing only a subset of connections, saving time in deployment of large-scale AI systems.
**Recurrent Updates and Stability:** In recurrent neural networks or iterative inference models, the steady-state can be described by linear equations (for linearized systems or certain feedback loops). Ensuring stability or computing the long-term effect of feedback (like in a SAFLA persistence update, if we interpret that as some feedback alignment mechanism) might reduce to solving $(I - W)x = c$ where $W$ is the weights of feedback (likely diagonally dominant if designed to converge). Using sublinear solvers, one could estimate the fixed-point of such a recurrent system more efficiently, aiding in real-time adjustments or stability checks. This is especially relevant for systems that layer many modules (each adding a small influence), because the resulting linear system has special structure exploitable by these algorithms.
**Anti-Hallucination and Truth Verification in AI:** Modern AI assistants use truth-verification layers to cross-check the facts an AI produces. One could imagine a truth-verification mechanism that sets up a large constraint graph of facts, sources, and consistency requirements. Solving this as a linear feasibility or least-squares problem might identify a self-consistent assignment of truth values or confidence (with diagonal dominance if each fact's own prior confidence outweighs contradictions). A sublinear solver can rapidly detect inconsistencies or propagate corrections by examining only relevant portions of the knowledge graph. In effect, it can perform a "consistency sweep" through a vast knowledge network without explicitly touching every node, which is analogous to how PageRank can find important pages without scanning the entire web. This fits well into anti-hallucination pipelines: the AI can quickly verify local consistency of certain claims by solving the corresponding sub-problem in sublinear time, catching potential errors faster.
In summary, any scenario that can be modeled as a large sparse system with a dominant self-term (which is common in stabilized or convergent systems) stands to gain. These new algorithms will accelerate verification and inference loops in complex systems, from graph analytics to multi-agent AI, by focusing computation where it matters most and leveraging the problem's inherent structure.
## Future Outlook
The advent of sublinear-time solvers for asymmetric systems is a significant leap in theory, but it also spurs practical questions. Implementing these algorithms in real-world systems (like very large distributed graphs or AI pipelines) will require careful engineering – one must be able to randomly access local neighborhoods in a graph efficiently, for example, to perform the random walk sampling. Fortunately, big-data processing frameworks and graph databases can be adapted for this purpose.
On the theory side, researchers note that their frameworks "open the door for further study into local graph algorithms and directed spectral graph theory." There is now a unifying lens to view problems like PageRank, influence maximization, current flows in directed networks, etc., which were previously handled with ad-hoc methods. We can expect more generalized algorithms that handle other classes of matrices (beyond diagonal dominance) in sublinear time, or tighter bounds for special graph families (e.g. nearly Eulerian graphs, or highly clustered networks). Also, the techniques might extend to solving nonlinear systems approximately by linearization and local solving, pushing the boundary of what "sublinear algorithms" can do in complex systems.
For AI systems specifically, integrating these solvers could lead to smarter resource allocation – e.g., an AI might decide on the fly which parts of a knowledge network to query (perform a "local solve" on) to verify a claim, rather than doing an exhaustive check. This aligns perfectly with the notion of focused, trust-aware computation: using heavy math machinery only where needed, thus reducing the risk of hallucination by constantly keeping the system's internal state in a verified, converged zone without incurring huge computation every time.
In conclusion, sublinear-time solvers for ADD systems combine deep theoretical innovation (generalizing spectral analysis to non-symmetric matrices) with highly practical outcomes (speeding up graph and AI computations). This development is directly relevant to accelerating truth verification and robust reasoning in large-scale AI swarms, ensuring that our increasingly complex systems remain fast, truthful, and reliable.
## References
- Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow. **On Solving Linear Systems in Sublinear Time.** ITCS 2019. (Introduces local solvers for SDD systems, showing polylog-time possible for well-conditioned cases) [drops.dagstuhl.de](https://drops.dagstuhl.de).
- Daniel A. Spielman, Shang-Hua Teng. **Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.** STOC 2004. (Breakthrough near-linear solver for SDD systems) [drops.dagstuhl.de](https://drops.dagstuhl.de).
- Tsz Chiu Kwok, Zhewei Wei, Mingji Yang. **On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time.** arXiv preprint 2509.13891 (Sept 2025). (General framework for sublinear ADD solvers; defines maximum $p$-norm gap and unifies forward/backward push methods) [arxiv.org/abs/2509.13891](https://arxiv.org/abs/2509.13891).
- Weiming Feng, Zelin Li, Pan Peng. **Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin–Johnsen Model.** arXiv preprint 2509.13112 (Sept 2025). (Alternate approach via probabilistic recurrence; handles general diagonally dominant matrices and applies to social network opinion dynamics) [arxiv.org/abs/2509.13112](https://arxiv.org/abs/2509.13112).