DagSemProc.09061.3.pdf
- Filesize: 137 kB
- 4 pages
Document
A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 9061
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2009-07-24
Cite As Get BibTex
Samuel I. Daitch and Daniel A. Spielman. A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/DagSemProc.09061.3
Abstract
We present an algorithm for solving a linear system in a symmetric M-matrix.
In particular, for $n times n$ symmetric M-matrix $M$, we show how to find a diagonal matrix $D$ such that
$DMD$ is diagonally-dominant. To compute $D$, the algorithm must solve $O{log n}$ linear systems in diagonally-dominant matrices. If we solve these diagonally-dominant systems approximately using the Spielman-Teng
nearly-linear time solver, then we obtain an algorithm for approximately solving linear systems in symmetric M-matrices, for which the expected running time is also nearly-linear.
Subject Classification
Keywords
- M-matrix
- diagonally-dominant matrix
- linear system solver
- iterative algorithm
- randomized algorithm
- network flow
- gain graph
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads