Keywords: H-matrix, non-negative matrix, irreducible matrix, spectral radius, Perron vector, Jacobi matrix.

The convergence of several iterative methods for solving linear systems , is guaranteed when the coefficient matrix is an H-matrix. In addition, it is known that several preconditioners are safely computed for this class of matrices. So, it is convenient to know if A is an H-matrix or not before applying these methods.

Recall that a real square matrix A is an H-matrix if its comparison matrix (where and if ) is an M-matrix, that is, if it can be expressed in the form , with and , where is the spectral radius of B. Some characterizations of a non-singular H-matrix are the following (see [1,2]):

Theorem 1 If A is a nonsingular matrix, then A is an H-matrix if, and only if,

where is the Jacobi matrix of A, with diag.

Theorem 2 A is an H-matrix if, and only if, there is a positive diagonal matrix diag, such that is strictly diagonally dominant, i.e.,

Otherwise, if there is a positive diagonal matrix diag, such that

then A is not generalized diagonally dominant and A is not an H-matrix.

Based in the last characterization, in [3,4], several algorithms are proposed to compute the matrix D to determine if a given matrix is an H-matrix or not. Moreover in [4] a generalization is proposed to compute the spectral radius of nonnegative matrices with constant diagonal entries. However, the algorithms in [3,4] can fail if the matrix A is reducible. Recall that a matrix A is reducible if a permutation matrix exists such that is a block triangular matrix, where the blocks and are square matrices, and it is irreducible if it is not reducible.

Moreover, using this decomposition recurrently, one can obtain a permutation matrix such that is a block triangular matrix where the diagonal blocks are irreducible or null matrices, which is called the "canonical form" of A.

In this work, we present several algorithms based on finding the matrix D that ensures the generalized diagonal dominance of the matrix. In the process of finding D, some useful information is obtained that permits the proposed algorithms in order to:

• Conclude if a given matrix is an H-matrix;
• Determine if a matrix is reducible, and, in this case, to find its canonical form;
• Compute the spectral radius of the Jacobi matrix associated to a Z-matrix (i.e. ) and Compute the Perron vector (unitary eigenvector associated to the spectral radius) of a non-negative matrix.

The algorithms require one parameter , the value of which can modify their performance. Usually, the value of is introduced by the user, but we propose a new approach in which is dynamically calculated by the algorithms themselves. We present several numerical results which show that, in general, the best results are obtained for a user-selected ; however, in some cases the algorithms fail. When is computed automatically, the algorithms run to completion and the best results are obtained by calculating as the geometrical mean of the maximum and minimum row sums.

When the matrix is reducible, we present some examples to show that it is possible to compute the spectral radius of the Jacobi matrix using the original matrix or its transpose. Moreover, when the algorithm stagnates, the results obtained can be applied to conclude that it is a reducible matrix and to determine the symmetric permutation of the matrix that allows to obtain its canonical form. Later, one can compute the spectral radius of irreducible diagonal blocks.

1

A. Berman and R. J. Plemmons, "Nonnegative matrices in the mathematical sciences", Comput. Sci. App. Math. Academic Press, London, 1979.

2

Richard S. Varga, "Matrix iterative analysis", Authomatic Computation. Prentice-Hall, New Jersey, 1962.

3

B. Li, L. Li, M. Harada, H. Niki, M. J. Tsatsomeros, "An iterative criterion for H-matrices", Linear Algebra Appl. 271: 179-190, 1998. doi:10.1016/S0024-3795(98)90070-2

4

L. Li, "On the iterative criterion for generalized diagonally dominant matrices", SIAM J. Matrix Anal. Appl., 24(1): 17-24, 2002. doi:10.1137/S0895479898348829

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 £105 +P&P)