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

Weiming Feng, Zelin Li, Pan Peng · 2025

Read Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model by Weiming Feng, Zelin Li, Pan Peng (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-13112.txt.

Introduction

Weiming Feng, Zelin Li and Pan Peng solve dominant linear systems in 2025 by reading only a sliver of the input. Dominant rows outweigh off-row sums, a trait in many network flows. Full solves waste time when one entry is all that is needed.

Random methods return one entry within a set error. They need just a small part of the matrix and right side. A matching lower bound proves one factor cannot be cut. Past work needed symmetric forms; the new path covers broad strict and some loose cases. A key use speeds opinion reads in the Friedkin and Johnsen model.

Catalog record

CREATORWeiming Feng, Zelin Li, Pan Peng
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE97 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-13112

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model Weiming Feng, Zelin Li, Pan Peng Abstract We study sublinear-time algorithms for solving linear systems S ​ z = b Sz=b , where S S is a diagonally dominant matrix, i.e., | S i ​ i | ≥ δ + ∑ j ≠ i | S i ​ j | |S_{ii}|\geq\delta+\sum_{j\neq i}|S_{ij}| for all i ∈ [ n ] i\in[n] , for some δ ≥ 0 \delta\geq 0 . We present randomized algorithms that, for any u ∈ [ n ] u\in[n] , return an estimate z u z_{u} of z u ∗ z^{*}_{u} with additive error ε \varepsilon or ε ​ ∥ z ∗ ∥ ∞ \varepsilon\lVert z^{*}\rVert_{\infty} , where z ∗ z^{*} is some solution to S ​ z ∗ = b Sz^{*}=b , and the algorithm only needs to read a small portion of the input S S and b b . For example, when the additive error is ε \varepsilon and assuming δ > 0 \delta>0 , we give an algorithm that runs in time O ⁡ ( ‖ b ‖ ∞ 2 ​ S max δ 3 ​ ε 2 ​ log ⁡ ‖ b ‖ ∞ δ ​ ε ) O\left(\frac{\|b\|_{\infty}^{2}S_{\max}}{\delta^{3}\varepsilon^{2}}\log\frac{\|b\|_{\infty}}{\delta\varepsilon}\right) , where S max = max i ∈ [ n ] ⁡ | S i ​ i | S_{\max}=\max_{i\in[n]}|S_{ii}| . We also prove a matching lower bound, showing that the linear dependence on S max S_{\max} 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 \delta>0 ) and a broader class of non-strictly diagonally dominant matrices ( δ = 0 ) (\delta=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. 1 Introduction Solving linear systems is a fundamental computational problem with numerous applications. Given a matrix A\in\mathbb{R}^{n\times n} and a vector b\in\mathbb{R}^{n} , the goal is to find a solution z\in\mathbb{R}^{n} satisfying Az=b . Numerous polynomial-time algorithms have been developed for this task. For example, researchers have established that, under exact arithmetic (RealRAM model), linear systems can be solved in O(n^{\omega}) time, where \omega<2.371339 is the matrix multiplication exponent [ 1 ] , through a reduction to fast matrix multiplication. When A is sparse, the conjugate gradient method applied to the normal equations A^{\top}Az=A^{\top}b solves the system in O(\mathrm{nnz}(A)\cdot n) time (see, for example, [ 30 ] ). Special classes of linear systems admit even faster algorithms. For instance, symmetric diagonally dominant (SDD) matrices—defined by the condition a_{ii}\geq\sum_{j\neq i}|a_{ij}| for all i —allow nearly linear-time solvers. This class includes the Laplacian matrix L_{G} of an undirected graph G . Beginning with the seminal work of Spielman and Teng [ 31 ] , a series of results have demonstrated that systems like L_{G}z=b can be solved in nearly linear time (e.g., [ 21 , 12 ] ). The current state-of-the-art runs in \tilde{O}(\mathrm{nnz}(A)\log(1/\varepsilon)) time, where \varepsilon is an accuracy parameter and \tilde{O}(\cdot) suppresses polylogarithmic factors. Extensions to directed graphs have also yielded nearly linear-time solvers for certain Laplacian systems (e.g., [ 11 ] ). Solving linear systems where the coefficient matrix is diagonally dominant (DD) also arises naturally in numerous practical settings, such as PageRank or Personalized PageRank (PPR), computing the effective resistance, and machine learning on graphs including semi-supervised learning and label propagation [ 32 , 18 ] . Motivated by advances in fast linear-system solvers under alternative computational models and the challenges posed by modern large-scale datasets, Andoni, Krauthgamer, and Pogrow [ 4 ] pioneered sublinear-time algorithms for solving diagonally dominant linear systems. These algorithms inspect only a sparse subset of the input (the matrix A and vector b ) while preserving rigorous guarantees on output quality. The work in [ 4 ] addresses settings where only one or a few coordinates of the solution z^{*}\in\mathbb{R}^{n} are sought. Focusing on SDD matrices S with non-negative diagonal entries, their algorithm assumes query access to both S and b , which corresponds to vertex queries and neighbor queries in the underlying graph. For any index u\in[n] , it computes an estimate \hat{z}_{u} approximating the u -th coordinate of a solution z^{*} to the system Sz=b . The runtime scales polynomially in \kappa , an upper bound on the condition number of S , and becomes sublinear in the input size when \kappa is small (see more discussions on the runtime below). This framework is applicable to a wide range of applications. Specifically, as noted in [ 4 ] , the problem of estimating effective resistances between pairs of vertices in graphs can be reduced to estimating a few coordinates of the solution to a Laplacian linear system. The corresponding algorithm was subsequently improved by Peng et al. [ 27 ] . Additionally, Neumann et al. [ 26 ] observed that such sublinear-time algorithms can be applied to determine the opinions of specific nodes in social networks within the Friedkin-Johnsen (FJ) model (see further discussions below). Furthermore, the development of sublinear-time linear system solvers has been influenced by recent advancements in quantum algorithms for linear systems [ 17 , 2 , 10 , 14 ] (see Section 1.3 ). While powerful, the algorithm in [ 4 ] is limited to SDD matrices with non-negative diagonal entries, which is a special class of positive semi-definite (PSD) matrices. Their approach involves treating the matrix S as the Laplacian matrix of an undirected graph G and performing short-length random walks on the corresponding graph. The estimates are then defined based on the outcomes of these random walks. This method inherently works only for S being symmetric and having non-negative diagonal entries. In this paper, we present new sublinear-time algorithms for solving linear systems as long as the matrix S is diagonally dominant, i.e., |S_{ii}|\geq\sum_{j\neq i}|S_{ij}| for all i . Note that S is not necessarily symmetric or constrained to have non-negative diagonal entries. In fact, such S is not necessarily PSD. We also provide a lower bound to demonstrate that our algorithm is nearly optimal. Finally, we apply our algorithm to obtain improved sublinear algorithms for opinion estimation in the Friedkin-Johnsen model. 1.1 Main results The problem and computational model We study the problem of estimating individual entries of the solution z^{*} to the linear system Sz=b in sublinear time, where S\in\mathbb{R}^{n\times n} is a \delta -diagonally dominant ( \delta -DD) matrix and b\in\mathbb{R}^{n} . The definition of \delta -DD matrix is given below. Definition 1.1 ( \delta -Diagonally Dominant ( \delta -DD) Matrix) . Let \delta\geq 0 be a non-negative parameter. A matrix S\in\mathbb{R}^{n\times n} is called \delta -diagonally dominant (or \delta -DD ) if \displaystyle\forall i\in[n],\quad|S_{ii}|\geq\delta+\sum_{j:j\neq i}|S_{ij}|. If \delta>0 , we say that S is strictly DD . If \delta=0 , we say S is non-strictly DD . Note that if S is strictly DD, then it is non-singular, so the solution z^{*} is unique. Now we specify the query model: the algorithm accesses the information of S and b through queries to an oracle. To define the oracle,

Read the complete text