A new criterion for the H-matrix property (Q1863291)

The comparison matrix \({\mathcal M}(A)=(\alpha_{ij}) \in {\mathbb R}^{n,n}\) of a matrix \(A=(a_{ij}) \in {\mathbb R}^{n,n}\) is defined by \(\alpha_{ii}=|a_{ii}|\), \(\alpha_{ij}=-|a_{ij}|\) if \(i \neq j\). A matrix is called an H-matrix if the eigenvalues of its comparison matrix have positive real parts. It is known that \(A\) is an H-matrix if and only if \(A\) is generalized strictly diagonally dominant, i.e. there exists a diagonal matrix \(D\) with positive entries such that \(AD\) is strictly diagonally dominant. The latter property is important in the proofs of convergence theorems for certain iterative methods to solve linear systems with \(A\), notably Gauss-Seidel, Jacobi and successive overrelaxation. The present authors construct an iterative algorithm that decides in a finite number of steps if a given matrix (irreducible and with at least one dominant diagonal element) is an H-matrix. The cost per iteration step is only \(O(n)\) where earlier methods had \(O(n^2)\). The authors prove this result and provide several numerical examples for small values of \(n\).