Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2003
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911217039179776 |
|---|---|
| author | Spielman, Daniel A. Teng, Shang-Hua |
| author_facet | Spielman, Daniel A. Teng, Shang-Hua |
| contents | We present a linear-system solver that, given an $n$-by-$n$ symmetric positive semi-definite, diagonally dominant matrix $A$ with $m$ non-zero entries and an $n$-vector $\bb $, produces a vector $\xxt$ within relative distance $ε$ of the solution to $A \xx = \bb$ in time $O (m^{1.31} \log (n κ_{f} (A)/ε)^{O (1)})$, where $κ_{f} (A)$ is the log of the ratio of the largest to smallest non-zero eigenvalue of $A$. In particular, $\log (κ_{f} (A)) = O (b \log n)$, where $b$ is the logarithm of the ratio of the largest to smallest non-zero entry of $A$. If the graph of $A$ has genus $m^{2θ}$ or does not have a $K_{m^θ} $ minor, then the exponent of $m$ can be improved to the minimum of $1 + 5 θ$ and $(9/8) (1+θ)$. The key contribution of our work is an extension of Vaidya's techniques for constructing and analyzing combinatorial preconditioners. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_cs_0310036 |
| institution | arXiv |
| publishDate | 2003 |
| record_format | arxiv |
| spellingShingle | Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$ Spielman, Daniel A. Teng, Shang-Hua Data Structures and Algorithms Numerical Analysis F.2.1; G.1.3 We present a linear-system solver that, given an $n$-by-$n$ symmetric positive semi-definite, diagonally dominant matrix $A$ with $m$ non-zero entries and an $n$-vector $\bb $, produces a vector $\xxt$ within relative distance $ε$ of the solution to $A \xx = \bb$ in time $O (m^{1.31} \log (n κ_{f} (A)/ε)^{O (1)})$, where $κ_{f} (A)$ is the log of the ratio of the largest to smallest non-zero eigenvalue of $A$. In particular, $\log (κ_{f} (A)) = O (b \log n)$, where $b$ is the logarithm of the ratio of the largest to smallest non-zero entry of $A$. If the graph of $A$ has genus $m^{2θ}$ or does not have a $K_{m^θ} $ minor, then the exponent of $m$ can be improved to the minimum of $1 + 5 θ$ and $(9/8) (1+θ)$. The key contribution of our work is an extension of Vaidya's techniques for constructing and analyzing combinatorial preconditioners. |
| title | Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$ |
| topic | Data Structures and Algorithms Numerical Analysis F.2.1; G.1.3 |
| url | https://arxiv.org/abs/cs/0310036 |