Keywords: H-matrix, comparison matrix, Frobenius normal form, irreducible and reducible matrices, classes of H-matrices.

H-matrices play an important role in the theory and applications of numerical linear algebra. If the coefficients matrix A is an H-matrix, most of the classical iterative methods for the solution of the problem at hand converge and the computation of several common preconditioners is guaranteed. So, it is very useful to know whether a given matrix is an H-matrix.

Different algorithms to determine H-matrices can be found in the literature. In [1] it is proved that the proposed algorithm (AH-algorithm) can determine if the matrix A is an H-matrix or not, when A is irreducible and its comparison matrix is nonsingular. The inclusion of the reducible case is an improvement of the same authors in [2]. Nevertheless, there some nonsingular H-matrices exist such that their comparison matrix is singular, and there are some singular H-matrices having some null diagonal entries [3], where the set of general H-matrices is partitioned in three classes: invertible class, mixed class, and singular class. Thus, to improve the AH-algorithm, one must include, besides reducible matrices, the mixed and singular cases. Furthermore, the differentiation of the H-matrices class is essential since the problems to consider are different.

The main objective of this work is to derive a new algorithm which will clarify the H-matrix character or not of a general square matrix and will make the distinction among the three classes of H-matrices. Moreover, the identification will be made in an efficient way.

Apart from some initial and intermediate steps, our algorithm has three parts. Specifically:

i)

The first part determines the irreducible/reducible character of a given matrix A.

ii)

The second part, which is skipped when A is irreducible, finds the row indexes to determine the diagonal blocks of the Frobenius normal form of A (maybe, in an irregular order).

iii)

In the third part, each diagonal block B(k) obtained in part (ii) is analyzed: null diagonal entries belong to 1x1 diagonal blocks (if not, A is not an H-matrix); for the remainder blocks, a slight modification of AH-algorithm is applied to clarify if B(k) belongs to invertible or mixed classes or B(k) (and also A) is a non-H-matrix. It should be pointed out that applying the AH-algorithm to irreducible matrices B(k) instead of to A itself, not only drastically reduces the number of maximal iterations in the AH-algorithm but also reduces the threshold of uncertainty for the mixed case.

The outline of the paper is the following. Firstly, a section including the background of the main results concerning H-matrices classes and reducibility is performed. In the next section the possibility of using the AH-algorithm to determine general H-matrices is discussed. In the main section, the material needed to construct the new algorithm is explained. Further, the determination of the H-matrix character and class is proved. Finally, a section including some numerical examples is given.

1

M. Alanelli, A. Hadjidimos, "A new iterative criterion for H-matrices", SIAM J. Matrix Anal. Appl., 29, 160-176, 2006. doi:10.1137/050636802

2

M. Alanelli, A. Hadjidimos, "A new iterative criterion for H-matrices: The reducible case", Linear Algebra Appl., 428, 2761-2777, 2008. doi:10.1016/j.laa.2007.12.020

3

R. Bru, C. Corral, I. Giménez, J. Mas, "Classes of general H-matrices", Linear Algebra Appl., 429, 2358-2366, 2008. doi:10.1016/j.laa.2007.10.030

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £125 +P&P)