2022/01/26 by Daitch, Samuel I., Spielman, Daniel A.
#M-matrix #diagonally-dominant matrix #gain graph #iterative algorithm #linear system solver #network flow #randomized algorithm
paper · doi:10.4230/dagsemproc.09061.3
We present an algorithm for solving a linear system in a symmetric M-matrix. In particular, for n times n symmetric M-matrix M, we show how to find a diagonal matrix D such that DMD is diagonally-dominant. To compute D, the algorithm must solve Olog n linear systems in diagonally-dominant matrices. If we solve these diagonally-dominant systems approximately using the Spielman-Teng nearly-linear time solver, then we obtain an algorithm for approximately solving linear systems in symmetric M-matrices, for which the expected running time is also nearly-linear.