SDDM系统逐项近似解的几乎线性时间算法 (Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time)

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.

翻译：本文提出一种算法，对于任意可逆对称对角占优M矩阵（SDDM），即图拉普拉斯矩阵的主子矩阵 $\boldsymbol{\mathit{L}}$ 与非负向量 $\boldsymbol{\mathit{b}}$，该算法能以高概率在 $\tilde{O}(m n^{o(1)})$ 时间内计算出 $\boldsymbol{\mathit{L}} \boldsymbol{\mathit{x}} = \boldsymbol{\mathit{b}}$ 解的逐项近似值，其中 $m$ 表示非零元素数量，$n$ 为系统维度。