A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix

Authors Samuel I. Daitch, Daniel A. Spielman



PDF
Thumbnail PDF

File

DagSemProc.09061.3.pdf
  • Filesize: 137 kB
  • 4 pages

Document Identifiers

Author Details

Samuel I. Daitch
Daniel A. Spielman

Cite AsGet 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.
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)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail