# Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model

arXiv: https://arxiv.org/abs/2509.13112 · HTML: https://mlsanity.com/paper/2509.13112/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 34 references that are in the map.
- First posted on arXiv 16 Sep 2025.

## Builds on (most cited first, 12 of 12)

- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [Quantum linear systems algorithms: a primer](https://mlsanity.com/paper/1802.08227/) (2018)
- [Quantum-inspired sublinear classical algorithms for solving low-rank linear systems](https://mlsanity.com/paper/1811.04852/) (2018)
- [Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations](https://mlsanity.com/paper/1811.10722/) (2018)
- [Local Algorithms for Estimating Effective Resistance](https://mlsanity.com/paper/2106.03476/) (2021)
- [Graph Laplacian for Semi-Supervised Learning](https://mlsanity.com/paper/2301.04956/) (2023)
- [Fast Bidirectional Probability Estimation in Markov Models](https://mlsanity.com/paper/1507.05998/) (2015)
- [On Solving Linear Systems in Sublinear Time](https://mlsanity.com/paper/1809.02995/) (2018)
- [Fast Evaluation for Relevant Quantities of Opinion Dynamics](https://mlsanity.com/paper/2101.08143/) (2021)
- [Sublinear-Time Opinion Estimation in the Friedkin--Johnsen Model](https://mlsanity.com/paper/2404.16464/) (2024)
- [Faster Spectral Density Estimation and Sparsification in the Nuclear Norm](https://mlsanity.com/paper/2406.07521/) (2024)

## Abstract (arXiv)

We study sublinear-time algorithms for solving linear systems Sz = b, where S is a diagonally dominant matrix, i.e., |Sii| ≥ δ + sumj ne i |Sij| for all i ∈ [n], for some δ ≥ 0. We present randomized algorithms that, for any u ∈ [n], return an estimate zu of z^*u with additive error varepsilon or varepsilon lVert z^*rVert_∞, where z^* is some solution to Sz^* = b, and the algorithm only needs to read a small portion of the input S and b. For example, when the additive error is varepsilon and assuming δ>0, we give an algorithm that runs in time Oleft( frac|b|_∞2 Smaxδ3 varepsilon2 log frac| b |_∞δ varepsilon right), where Smax = maxi ∈ [n] |Sii|. We also prove a matching lower bound, showing that the linear dependence on Smax is optimal. Unlike previous sublinear-time algorithms, which apply only to symmetric diagonally dominant matrices with non-negative diagonal entries, our algorithm works for general strictly diagonally dominant matrices (δ > 0) and a broader class of non-strictly diagonally dominant matrices (δ = 0). Our approach is based on analyzing a simple probabilistic recurrence satisfied by the solution. As an application, we obtain an improved sublinear-time algorithm for opinion estimation in the Friedkin--Johnsen model.