Details

Autor(en) / Beteiligte

• Boman, Erik G.
• Chen, Doron
• Hendrickson, Bruce
• Toledo, Sivan

Titel

Maximum-weight-basis preconditioners

Ist Teil von

• Numerical linear algebra with applications, 2004-10, Vol.11 (8-9), p.695-721

Ort / Verlag

Chichester, UK: John Wiley & Sons, Ltd

Erscheinungsjahr

2004

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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+t2) nonzeros, where n is the dimension of the matrix and 1⩽t⩽n is a parameter that one can choose. Their construction is efficient and guarantees that the condition number of the preconditioned system is O(n2/t2) 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. Copyright © 2004 John Wiley & Sons, Ltd.