×

Stable LU factorization of H-matrices. (English) Zbl 0637.65022

This paper shows that an appropriate form of Gaussian elimination is applicable to H-matrices. If A is an arbitrary real matrix it is called an M-matrix if \(a_{ij}\leq 0\) for \(i\neq j\) and if all its eigenvalues have non-negative real part. The comparison matrix \({\mathcal M}(A)\equiv m_{ij}\) of any square complex matrix A is defined by \(m_{ii}=| a_{ii}|\), \(m_{ij}=-| a_{ij}|\), \(i\neq j\). Such an A is an H-matrix if \({\mathcal M}(A)\) is an M-matrix. Any square matrix A is column diagonally dominant (cdd) if \(\exists\) scalars \(d_ i>0\) such that \(d_ j| a_{jj}| \geq \sum_{i\neq j}d_ i| a_{ij}|,\) \(1\leq j\leq n\) I. Kuo [ibid. 16, 217-220 (1977; Zbl 0353.15021)] has shown that \(\exists\) a permutation matrix P such that \(PAP^ T\) admits an LU factorization into M-matrices and a numerically stable algorithm for the computation is given by the first and the third author [SIAM J. Algebraic Discrete Methods 7, 368-378 (1986; Zbl 0613.65027)]. The current authors extend this result to H-matrices and also show that the computed factorization is numerically stable. Further, it is shown that the growth factor \(\gamma\) resulting from application of Gaussian elimination with cdd pivoting is bounded above by n, the size of A.
Reviewer: A.Swift

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
Full Text: DOI

References:

[1] Ahac, A. A.; Olesky, D. D., A stable method for the LU factorization of \(M\)-matrices, SIAM J. Algebraic Discrete Methods, 7, 368-378 (1986) · Zbl 0613.65027
[2] Berman, A.; Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences (1979), Academic: Academic New York · Zbl 0484.15016
[3] Carlson, D.; Markham, T. L., Schur complements of diagonally dominant matrices, Czechoslovak Math. J., 29, 246-251 (1979) · Zbl 0423.15008
[4] Fan, K., Note on \(M\)-matrices, Quart. J. Math. Oxford Ser., 11, 2, 43-49 (1960) · Zbl 0104.01203
[5] Funderlic, R. E.; Neumann, M.; Plemmons, R. J., LU decompositions of generalized diagonally dominant matrices, Numer. Math., 40, 57-69 (1982) · Zbl 0481.65017
[6] C.R. Johnson, private communication.; C.R. Johnson, private communication.
[7] Kuo, I., A note on factorizations of singular \(M\)-matrices, Linear Algebra Appl., 16, 217-220 (1977) · Zbl 0353.15021
[8] Lau, C. M.; Markham, T. L., LU Factorizations, Czechoslovak Math. J., 29, 546-550 (1979) · Zbl 0431.65013
[9] Neumann, M., On the Schur complement and the LU-factorization of a matrix, Linear and Multilinear Algebra, 9, 241-254 (1981) · Zbl 0455.15013
[10] Neumann, M.; Plemmons, R. J., Backward error analysis for linear systems associated with inverses of \(H\)-matrices, BIT, 24, 102-112 (1984) · Zbl 0557.65019
[11] Stewart, G. W., Introduction to Matrix Computations (1973), Academic: Academic New York · Zbl 0302.65021
[12] Varga, R. S., On recurring theorems on diagonal dominance, Linear Algebra Appl., 13, 1-9 (1976) · Zbl 0336.15007
[13] Varga, R. S.; Cai, D.-Y., On the LU factorization of \(M\)-matrices, Numer. Math., 38, 179-192 (1981) · Zbl 0477.65021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.