Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$

Details Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$ Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$

2003-10-17

arxiv.org/abs/cs/0310036v2

Computer Science

Data Structures and Algorithms

fixed a typo on page 9

Scientific paper

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 $\epsilon$ of the solution to $A \xx = \bb$ in time $O (m^{1.31} \log (n \kappa_{f} (A)/\epsilon)^{O (1)})$, where $\kappa_{f} (A)$ is the log of the ratio of the largest to smallest non-zero eigenvalue of $A$. In particular, $\log (\kappa_{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\theta}$ or does not have a $K_{m^{\theta}} $ minor, then the exponent of $m$ can be improved to the minimum of $1 + 5 \theta $ and $(9/8) (1+\theta)$. The key contribution of our work is an extension of Vaidya's techniques for constructing and analyzing combinatorial preconditioners.

Affiliated with

Also associated with

No associations

Rating

Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$ 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 Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-439772