A fast and stable test to check if a weakly diagonally dominant matrix is a nonsingular M-matrix

Azimzadeh, Parsiad

doi:10.1090/mcom/3347

A fast and stable test to check if a weakly diagonally dominant matrix is a nonsingular M-matrix
HTML articles powered by AMS MathViewer

by Parsiad Azimzadeh HTML | PDF

Math. Comp. 88 (2019), 783-800 Request permission

Abstract:

We present a test for determining if a substochastic matrix is convergent. By establishing a duality between weakly chained diagonally dominant (w.c.d.d.) L-matrices and convergent substochastic matrices, we show that this test can be trivially extended to determine whether a weakly diagonally dominant (w.d.d.) matrix is a nonsingular M-matrix. The test’s runtime is linear in the order of the input matrix if it is sparse, and quadratic if it is dense. This is a partial strengthening of the cubic test in [J. M. Peña., A stable test to check if a matrix is a nonsingular M-matrix, Math. Comp., 247, 1385–1392, 2004]. As a by-product of our analysis, we prove that a nonsingular w.d.d. M-matrix is a w.c.d.d. L-matrix, a fact whose converse has been known since at least 1964.

References

P. Azimzadeh and P. A. Forsyth, Weakly chained matrices, policy iteration, and impulse control, SIAM J. Numer. Anal. 54 (2016), no. 3, 1341–1364. MR 3493959, DOI 10.1137/15M1043431
Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Classics in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. Revised reprint of the 1979 original. MR 1298430, DOI 10.1137/1.9781611971262
Olivier Bokanowski, Stefania Maroso, and Hasnaa Zidani, Some convergence results for Howard’s algorithm, SIAM J. Numer. Anal. 47 (2009), no. 4, 3001–3026. MR 2551155, DOI 10.1137/08073041X
J. H. Bramble and B. E. Hubbard, On a finite difference analogue of an elliptic boundary problem which is neither diagonally dominant nor of non-negative type, J. Math. and Phys. 43 (1964), 117–132. MR 162367
Guang-Hui Cheng and Ting-Zhu Huang, An upper bound for $\Vert A^{-1}\Vert _\infty$ of strictly diagonally dominant $M$-matrices, Linear Algebra Appl. 426 (2007), no. 2-3, 667–673. MR 2350685, DOI 10.1016/j.laa.2007.06.001
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to algorithms, 3rd ed., MIT Press, Cambridge, MA, 2009. MR 2572804
F. R. Gantmacher, Applications of the theory of matrices, Interscience Publishers, Inc., New York; Interscience Publishers Ltd., London, 1959. Translated by J. L. Brenner, with the assistance of D. W. Bushaw and S. Evanusa. MR 0107648
Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913
Nicholas J. Higham, The accuracy of floating point summation, SIAM J. Sci. Comput. 14 (1993), no. 4, 783–799. MR 1223274, DOI 10.1137/0914050
Ting-Zhu Huang and Yan Zhu, Estimation of $\|A^{-1}\|_\infty$ for weakly chained diagonally dominant $M$-matrices, Linear Algebra Appl. 432 (2010), no. 2-3, 670–677. MR 2577710, DOI 10.1016/j.laa.2009.09.012
Chaoqian Li and Yaotang Li, Weakly chained diagonally dominant $B$-matrices and error bounds for linear complementarity problems, Numer. Algorithms 73 (2016), no. 4, 985–998. MR 3579726, DOI 10.1007/s11075-016-0125-8
Chaoqian Li, Yaotang Li, and Ruijuan Zhao, New inequalities for the minimum eigenvalue of $M$-matrices, Linear Multilinear Algebra 61 (2013), no. 9, 1267–1279. MR 3175363, DOI 10.1080/03081087.2012.746332
Chaoqian Li, Ruidan Ma, Qilong Liu, and Yaotang Li, Subdirect sums of weakly chained diagonally dominant matrices, Linear Multilinear Algebra 65 (2017), no. 6, 1220–1231. MR 3615539, DOI 10.1080/03081087.2016.1233933
Wen Li, The infinity norm bound for the inverse of nonsingular diagonal dominant matrices, Appl. Math. Lett. 21 (2008), no. 3, 258–263. MR 2433738, DOI 10.1016/j.aml.2007.03.018
J. M. Peña, A stable test to check if a matrix is a nonsingular $M$-matrix, Math. Comp. 73 (2004), no. 247, 1385–1392. MR 2047092, DOI 10.1090/S0025-5718-04-01639-4
R. J. Plemmons, $M$-matrix characterizations. I. Nonsingular $M$-matrices, Linear Algebra Appl. 18 (1977), no. 2, 175–188. MR 444681, DOI 10.1016/0024-3795(77)90073-8
Yousef Saad, Iterative methods for sparse linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR 1990645, DOI 10.1137/1.9780898718003
P. N. Shivakumar and Kim Ho Chew, A sufficient condition for nonvanishing of determinants, Proc. Amer. Math. Soc. 43 (1974), 63–66. MR 332820, DOI 10.1090/S0002-9939-1974-0332820-0
P. N. Shivakumar, Joseph J. Williams, Qiang Ye, and Corneliu A. Marinov, On two-sided bounds related to weakly diagonally dominant $M$-matrices with application to digital circuit dynamics, SIAM J. Matrix Anal. Appl. 17 (1996), no. 2, 298–312. MR 1384509, DOI 10.1137/S0895479894276370
Gui-Xian Tian and Ting-Zhu Huang, Inequalities for the minimum eigenvalue of $M$-matrices, Electron. J. Linear Algebra 20 (2010), 291–302. MR 2653540, DOI 10.13001/1081-3810.1374
Richard S. Varga, Matrix iterative analysis, Second revised and expanded edition, Springer Series in Computational Mathematics, vol. 27, Springer-Verlag, Berlin, 2000. MR 1753713, DOI 10.1007/978-3-642-05156-2
Feng Wang and De-shu Sun, Some new inequalities for the minimum eigenvalue of $M$-matrices, J. Inequal. Appl. , posted on (2015), 2015:195, 7. MR 3357017, DOI 10.1186/s13660-015-0723-3
Ping Wang, An upper bound for $\Vert A^{-1}\Vert _\infty$ of strictly diagonally dominant $M$-matrices, Linear Algebra Appl. 431 (2009), no. 5-7, 511–517. MR 2535528, DOI 10.1016/j.laa.2009.02.037
Ming Xu, Suhua Li, and Chaoqian Li, Inequalities for the minimum eigenvalue of doubly strictly diagonally dominant $M$-matrices, J. Appl. Math. , posted on (2014), Art. ID 535716, 8. MR 3253625, DOI 10.1155/2014/535716
Zhanshan Yang, Bing Zheng, and Xilan Liu, A new upper bound for $\|A^{-1}\|$ of a strictly $\alpha$-diagonally dominant $M$-matrix, Adv. Numer. Anal. , posted on (2013), Art. ID 980615, 6. MR 3149442, DOI 10.1155/2013/980615
Jianxing Zhao and Caili Sang, Several new inequalities for the minimum eigenvalue of $M$-matrices, J. Inequal. Appl. , posted on (2016), Paper No. 119, 9. MR 3486018, DOI 10.1186/s13660-016-1062-8