Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914165748137984 |
|---|---|
| author | Farfan, Angelo Ghadiri, Mehrdad Yang, Junzhao |
| author_facet | Farfan, Angelo Ghadiri, Mehrdad Yang, Junzhao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_16570 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time Farfan, Angelo Ghadiri, Mehrdad Yang, Junzhao Data Structures and Algorithms Numerical Analysis 65F10 F.2.1; G.1.3 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. |
| title | Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time |
| topic | Data Structures and Algorithms Numerical Analysis 65F10 F.2.1; G.1.3 |
| url | https://arxiv.org/abs/2511.16570 |