Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Accurate computation of the smallest eigenvalue of a diagonally dominant $M$-matrix

Authors: Attahiru Sule Alfa, Jungong Xue and Qiang Ye
Journal: Math. Comp. 71 (2002), 217-236
MSC (2000): Primary 65F18, 65F05
Published electronically: May 14, 2001
MathSciNet review: 1862996
Full-text PDF

Abstract | References | Similar Articles | Additional Information


If each off-diagonal entry and the sum of each row of a diagonally dominant $M$-matrix are known to certain relative accuracy, then its smallest eigenvalue and the entries of its inverse are known to the same order relative accuracy independent of any condition numbers. In this paper, we devise algorithms that compute these quantities with relative errors in the magnitude of the machine precision. Rounding error analysis and numerical examples are presented to demonstrate the numerical behaviour of the algorithms.

References [Enhancements On Off] (What's this?)

  • 1. A. Ahac and D. Olesky, A stable method for the LU factorization of $M$-matrices, SIAM J. Alg. Disc. Meth., 7(1986):368-378. MR 87i:65035
  • 2. J. Abate, L. Choudhury and W. Whitt, Asymptotics for steady-state tail probabilities in structured Markov queueing models, Commun. Statist-Stochastic Models, 1(1994):99-143. MR 95f:60106
  • 3. A.S. Alfa, J. Xue and Q. Ye, Entrywise perturbation theory for diagonally dominant $M$-matrices with applications, to appear in Numer. Math.
  • 4. J. Barlow and J. Demmel, Computing accurate eigensystems of scaled diagonally dominant matrices, SIAM J. Num. Anal., 27(3), (1990):762-791. MR 91g:65071
  • 5. A. Berman and R. Plemmons, Nonnegative matrices in mathematical science, Academic Press, New York, 1979. MR 82b:15013
  • 6. S. Conte and C. de Boor, Elementary numerical analysis Third edition, New York-Tokyo:McGraw-Hill 1980.
  • 7. J. Demmel and W. Kahan, Accurate singular values of bidiagonal matrices, SIAM J. Sci. Stat. Comput, 11(5)(1990):873-912. MR 91i:65072
  • 8. J. Demmel, Accurate SVDs of structured matrices, LAPACK Working Note #130, Dept. of Computer Science, Univ. of Tennessee, Oct. 1977.
  • 9. J. Demmel, M. Gu, S. Eisenstat, I. Slapnicar, K. Vaselic and Z. Dramc, Computing the singular value decomposition with high relative accuracy, Linear Algebra Appl. 299(1999):21-80. MR 2000j:65044
  • 10. L. Elsner, Inverse iteration for calculating the spectral radius of a nonnegative irreducible matrix, Linear Algebra Appl., 15(1976):235-242. MR 56:12026
  • 11. L. Elsner, I. Koltracht, M.Neumann and D.Xiao, On accurate computations of the Perron root, SIAM J. Matrix Anal. Appl., 14(1993):456-467. MR 93m:65057
  • 12. E. Falkenberg, On the asymptotic behaviour of the stationary distribution of Markov chains of M/G/1 type, Commun. Statist.-Stochastic Models, 10(1994):75-97. MR 94i:60111
  • 13. G. Golub and C. Van Loan, Matrix Computations, 2nd ed., The Johns Hopkins University Press, Baltimore, MD,1989. MR 90d:65055
  • 14. W.K. Grassmann, M.J. Taksar and D.P. Heyman, Regenerative analysis and steady-state distributions for Markov chains, Oper. Res., 33(1985):1107-1116. MR 82k:60125
  • 15. R. Gregory and D. Karney, A collection of matrices for testing computational Algorithm, Wiley, New York, 1969. MR 40:6752
  • 16. N.J. Higham A survey of componentwise perturbation theory in numerical linear algebra, Proc. Sympos. Appl. Math., Amer. Math. Soc., Providence, R.I., 48:49-77, 1994. MR 96a:65065
  • 17. T. Noda, Note on the computation of maximal eigenvalue of a nonnegative irreducible matrix, Numer. Math., 17(1971):382-386. MR 45:4620
  • 18. C. O'Cinneide, Entrywise perturbation theory and error analysis for Markov chains, Numer. Math., 65(1993):109-120.
  • 19. C. O'Cinneide, Relative-error bounds for the LU decomposition via the GTH algorithm, Numer. Math., 73(1996):507-519. MR 97h:65033
  • 20. C. O'Cinneide, Private communication.
  • 21. G. Robertazzi Computer networks and systems: queueing theory and performance evaluation, Springer-Verlag, 1990.
  • 22. P. Shivakumar, J. Williams, Q. Ye, C. Marinov, On two-sided bounds related to weakly diagonally dominant $M$-matrices with applications to digital circuit dynamics, SIAM J. Matrix Anal. Appl. 17(1996):298-312. MR 97c:15030
  • 23. R. Skeel, Iterative refinement implies numerical stability for Gaussian elimination, Math. Comp. 35:817-832, 1980. MR 83e:65058
  • 24. J.H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, 1965. MR 32:1894
  • 25. J.Xue and E.Jiang, Entrywise relative perturbation theory for nonsingular $M$-matrices and applications, BIT, 35(1995):417-427. MR 97k:65070
  • 26. J.Xue Computing the smallest eigenvalue of an $M$-matrix, SIAM J. Matrix Anal. Appl., 17(1996):748-762. MR 97g:65081

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65F18, 65F05

Retrieve articles in all journals with MSC (2000): 65F18, 65F05

Additional Information

Attahiru Sule Alfa
Affiliation: Department of Industrial and Manufacturing Systems Engineering, University of Windsor, Windsor, Ontario, Canada N9B 3P4

Jungong Xue
Affiliation: Fakultaet fuer Mathematik, Technishe Universitaet Chemnitz, Reichenhainer Str. 41, 09126 Chemnitz, Germany
Address at time of publication: Department of Industrial and Manufacturing Systems Engineering, University of Windsor, Windsor, Ontario, Canada N9B 3P4

Qiang Ye
Affiliation: Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506-0027

Keywords: Entrywise perturbation, diagonal dominant matrix, $M$-matrix, eigenvalue
Received by editor(s): March 22, 1999
Received by editor(s) in revised form: March 14, 2000
Published electronically: May 14, 2001
Additional Notes: Research of the first author was supported by grant No. OGP0006854 from Natural Sciences and Engineering Research Council of Canada
Research of the second author was supported by Natural Sciences Foundation of China and Alexander von Humboldt Foundation of Germany.
Research of the third author was supported by grants from University of Manitoba Research Development Fund and Natural Sciences and Engineering Research Council of Canada while this author was with University of Manitoba, Winnipeg, Manitoba, Canada
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society