Premium
Maximum‐weight‐basis preconditioners
Author(s) -
Boman Erik G.,
Chen Doron,
Hendrickson Bruce,
Toledo Sivan
Publication year - 2004
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.343
Subject(s) - mathematics , diagonal , dimension (graph theory) , matrix (chemical analysis) , convergence (economics) , simple (philosophy) , basis (linear algebra) , condition number , bounded function , combinatorics , block matrix , discrete mathematics , mathematical analysis , eigenvalues and eigenvectors , geometry , philosophy , materials science , physics , epistemology , quantum mechanics , economics , composite material , economic growth
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 2 ) 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 ( n 2 / t 2 ) 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.