Daitch, Samuel I. ;
Spielman, Daniel A.
A NearlyLinear Time Algorithm for Approximately Solving Linear Systems in a Symmetric MMatrix
Abstract
We present an algorithm for solving a linear system in a symmetric Mmatrix.
In particular, for $n times n$ symmetric Mmatrix $M$, we show how to find a diagonal matrix $D$ such that
$DMD$ is diagonallydominant. To compute $D$, the algorithm must solve $O{log n}$ linear systems in diagonallydominant matrices. If we solve these diagonallydominant systems approximately using the SpielmanTeng
nearlylinear time solver, then we obtain an algorithm for approximately solving linear systems in symmetric Mmatrices, for which the expected running time is also nearlylinear.
BibTeX  Entry
@InProceedings{daitch_et_al:DSP:2009:2080,
author = {Samuel I. Daitch and Daniel A. Spielman},
title = {A NearlyLinear Time Algorithm for Approximately Solving Linear Systems in a Symmetric MMatrix},
booktitle = {Combinatorial Scientific Computing},
year = {2009},
editor = {Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
number = {09061},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2080},
annote = {Keywords: Mmatrix, diagonallydominant matrix, linear system solver, iterative algorithm, randomized algorithm, network flow, gain graph}
}
2009
Keywords: 

Mmatrix, diagonallydominant matrix, linear system solver, iterative algorithm, randomized algorithm, network flow, gain graph 
Seminar: 

09061  Combinatorial Scientific Computing

Related Scholarly Article: 


Issue date: 

2009 
Date of publication: 

2009 