Back to Search
Start Over
Maximum-weight-basis preconditioners.
- Source :
- Numerical Linear Algebra with Applications; Oct/Nov2004, Vol. 11 Issue 8/9, p695-721, 27p
- Publication Year :
- 2004
-
Abstract
- This paper analyses a novel method for constructing preconditioners for diagonally dominant symmetric positive-definite matrices. The method discussed here is based on a simple idea: we construct M by simply dropping offdiagonal non-zeros from A and modifying the diagonal elements to maintain a certain row-sum property. The preconditioners are extensions of Vaidya's augmented maximum-spanning-tree preconditioners. The preconditioners presented here were also mentioned by Vaidya in an unpublished manuscript, but without a complete analysis. The preconditioners that we present have only O(n+t<superscript>2</superscript>) nonzeros, where n is the dimension of the matrix and 1&les;t&les;n is a parameter that one can choose. Their construction is efficient and guarantees that the condition number of the preconditioned system is O(n<superscript>2</superscript>/t<superscript>2</superscript>) if the number of nonzeros per row in the matrix is bounded by a constant. We have developed an efficient algorithm to construct these preconditioners and we have implemented it. We used our implementation to solve a simple model problem; we show the combinatorial structure of the preconditioners and we present encouraging convergence results. [ABSTRACT FROM AUTHOR]
- Subjects :
- MATRICES (Mathematics)
ALGEBRA
ALGORITHMS
STOCHASTIC convergence
NUMERICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 10705325
- Volume :
- 11
- Issue :
- 8/9
- Database :
- Complementary Index
- Journal :
- Numerical Linear Algebra with Applications
- Publication Type :
- Academic Journal
- Accession number :
- 14541855
- Full Text :
- https://doi.org/10.1002/nla.343