Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time

Angelo Farfan; Mehrdad Ghadiri; Junzhao Yang

doi:10.1145/3798129.3800770

STOC2026顶会

Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time

Angelo Farfan, Mehrdad Ghadiri, Junzhao Yang

arXiv DOI 出版方

2026年份

摘要

We present an algorithm that given any invertible symmetric diagonally dominant M-matrix (SDDM), i.e., a principal submatrix of a graph Laplacian, L and a nonnegative vector b, computes an entrywise approximation to the solution of L x = b in Õ(m no(1)) time with high probability, where m is the number of nonzero entries and n is the dimension of the system.