Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time

Abstract

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 $Lx=b$ in $\tilde{O}(m{n}^{o(1)})$ time with high probability, where $m$ is the number of nonzero entries and $n$ is the dimension of the system.