Self-Corrective Iterations (SCI) for generalized diagonally dominant matrices

摘要

A suggestive indicator is proposed for predicting whether a given (complex or real) square matrix A is or is not a generalized diagonally dominant matrix (GDDM) by which we mean if A can be brought into a strictly diagonally dominant matrix by post-multiplying some diagonal matrix D. Based on the indicator, three self-corrective iterative algorithms (SCI) are presented for determining if an irreducible A is or is not a GDDM and at the same time delivering the matrix D in case when A is a GDDM. The basic idea is to push A towards being (strictly) diagonally dominant when the indicator suggests that A is likely a GDDM or towards being off-diagonally dominant otherwise. Among the three algorithms, each has their own feature: one takes the fewest number of iterations but the most amount of work per iteration, one takes the most number of iterations but the least amount of work per iteration, and the third one strikes a balance between the two extremes. It is shown that the algorithms will terminate in finite many steps under the assumption that A has no zero entries and the comparison matrix of A is nonsingular. Comparing with existing methods, new algorithms are more efficient, as demonstrated on known difficult examples in the literature, newly designed random matrices, as well as matrices from the University of Florida Sparse Matrix Collection.