Abstract:
This paper analyzes 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 off-diagonal nonzeros 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 t is a paramater 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 implementatino to solve a simple model problem; we show the combinatorial structure of the preconditioners and we present encouraging convergence results.