Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

Details Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

2006-07-24

arxiv.org/abs/cs/0607105v4

Computer Science

Numerical Analysis

This is the version we have submitted

Scientific paper

We present a randomized algorithm that, on input a symmetric, weakly diagonally dominant $n$-by-$n$ matrix $A$ with $m$ non-zero entries and an $n$-vector $\bb$, produces an $\xxtil $ such that $\norm{\xx - \xxtil}_{A} \leq \epsilon \norm{\xx}_{A}$, where $A\xx=\bb$, in expected time $m \log^{O (1)}n \log (1/\epsilon)$. The algorithm applies subgraph preconditioners in a recursive fashion. These preconditioners improve upon the subgraph preconditioners first introduced by Vaidya (1990). For any symmetric, weakly diagonally-dominant matrix $A$ with non-positive off-diagonal entries and $k \geq 1$, we construct in time $m \log^{O (1)} n$ a preconditioner of $A$ with at most $2 (n - 1+ k)$ non-zero off-diagonal entries such that the preconditioned system has condition number at most $(n/k) \log^{O (1)} n$. If the non-zero structure of the matrix is planar, then the condition number is at most $(n/k) \log^{2} n \log \log n$, and the corresponding linear system solver runs in expected time $O (n \log^{2} n \log \log n \log (1/\epsilon))$. Similar bounds are obtained on the running time of algorithms computing approximate Fiedler vectors.

Affiliated with

Also associated with

No associations

Rating

Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-584806