Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Author: Parsiad Azimzadeh
Journal: Math. Comp. 88 (2019), 783-800
MSC (2010): Primary 65F30, 15B48, 15B51; Secondary 65F50
Published electronically: May 29, 2018
MathSciNet review: 3882284
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65F30, 15B48, 15B51, 65F50

Retrieve articles in all journals with MSC (2010): 65F30, 15B48, 15B51, 65F50

Additional Information

Parsiad Azimzadeh
Affiliation: David R. Cheriton School of Computer Science, University of Waterloo, Waterloo ON, Canada N2L 3G1
Address at time of publication: Department of Mathematics, University of Michigan, East Hall, 530 Church Street, Ann Arbor, Michigan 48109
MR Author ID: 1097701

Keywords: M-matrix, substochastic matrix, diagonally dominant, weakly chained diagonally dominant, sparse matrix
Received by editor(s): January 24, 2017
Received by editor(s) in revised form: June 11, 2017, November 14, 2017, and December 14, 2017
Published electronically: May 29, 2018
Article copyright: © Copyright 2018 American Mathematical Society