{"ID":2839181,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.16570","arxiv_id":"2511.16570","title":"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, $\\boldsymbol{\\mathit{L}}$ and a nonnegative vector $\\boldsymbol{\\mathit{b}}$, computes an entrywise approximation to the solution of $\\boldsymbol{\\mathit{L}} \\boldsymbol{\\mathit{x}} = \\boldsymbol{\\mathit{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.","short_abstract":"We present an algorithm that given any invertible symmetric diagonally dominant M-matrix (SDDM), i.e., a principal submatrix of a graph Laplacian, $\\boldsymbol{\\mathit{L}}$ and a nonnegative vector $\\boldsymbol{\\mathit{b}}$, computes an entrywise approximation to the solution of $\\boldsymbol{\\mathit{L}} \\boldsymbol{\\ma...","url_abs":"https://arxiv.org/abs/2511.16570","url_pdf":"https://arxiv.org/pdf/2511.16570v1","authors":"[\"Angelo Farfan\",\"Mehrdad Ghadiri\",\"Junzhao Yang\"]","published":"2025-11-20T17:27:40Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.NA\"]","methods":"[]","has_code":false}