Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
By: Angelo Farfan, Mehrdad Ghadiri, Junzhao Yang
Potential Business Impact:
Solves hard math problems much faster for computers.
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.
Similar Papers
Entrywise Approximate Matrix Inversion
Data Structures and Algorithms
Makes computers solve hard math problems faster.
Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model
Data Structures and Algorithms
Find answers to math problems faster.
On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
Data Structures and Algorithms
Solves complex math problems faster than before.