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

A suggestive indicator is proposed for predicting whether a given (complex or real) square matrix AA is or is not a generalized diagonally dominant matrix (GDDM) by which we mean if AA can be brought into a strictly diagonally dominant matrix by post-multiplying some diagonal matrix DD. Based on the indicator, three self-corrective iterative algorithms (SCI) are presented for determining if an irreducible AA is or is not a GDDM and at the same time delivering the matrix DD in case when AA is a GDDM. The basic idea is to push AA towards being (strictly) diagonally dominant when the indicator suggests that AA 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 AA has no zero entries and the comparison matrix of AA 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.