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

HTML articles powered by AMS MathViewer

- by Attahiru Sule Alfa, Jungong Xue and Qiang Ye;
- Math. Comp.
**71**(2002), 217-236 - DOI: https://doi.org/10.1090/S0025-5718-01-01325-4
- Published electronically: May 14, 2001
- PDF | Request permission

## Abstract:

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

- Alan A. Ahac and D. D. Olesky,
*A stable method for the $LU$ factorization of $M$-matrices*, SIAM J. Algebraic Discrete Methods**7**(1986), no. 3, 368–378. MR**844039**, DOI 10.1137/0607042 - Joseph Abate, Gagan L. Choudhury, and Ward Whitt,
*Asymptotics for steady-state tail probabilities in structured Markov queueing models*, Comm. Statist. Stochastic Models**10**(1994), no. 1, 99–143. MR**1259856**, DOI 10.1080/15326349408807290 - A.S. Alfa, J. Xue and Q. Ye,
*Entrywise perturbation theory for diagonally dominant $M$-matrices with applications,*to appear in Numer. Math. - Jesse Barlow and James Demmel,
*Computing accurate eigensystems of scaled diagonally dominant matrices*, SIAM J. Numer. Anal.**27**(1990), no. 3, 762–791. MR**1041262**, DOI 10.1137/0727045 - Abraham Berman and Robert J. Plemmons,
*Nonnegative matrices in the mathematical sciences*, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. MR**544666** - S. Conte and C. de Boor,
*Elementary numerical analysis*Third edition, New York-Tokyo:McGraw-Hill 1980. - James Demmel and W. Kahan,
*Accurate singular values of bidiagonal matrices*, SIAM J. Sci. Statist. Comput.**11**(1990), no. 5, 873–912. MR**1057146**, DOI 10.1137/0911052 - J. Demmel,
*Accurate SVDs of structured matrices,*LAPACK Working Note #130, Dept. of Computer Science, Univ. of Tennessee, Oct. 1977. - James Demmel, Ming Gu, Stanley Eisenstat, Ivan Slapničar, Krešimir Veselić, and Zlatko Drmač,
*Computing the singular value decomposition with high relative accuracy*, Linear Algebra Appl.**299**(1999), no. 1-3, 21–80. MR**1723709**, DOI 10.1016/S0024-3795(99)00134-2 - Ludwig Elsner,
*Inverse iteration for calculating the spectral radius of a non-negative irreducible matrix*, Linear Algebra Appl.**15**(1976), no. 3, 235–242. MR**453772**, DOI 10.1016/0024-3795(76)90029-x - L. Elsner, I. Koltracht, M. Neumann, and D. Xiao,
*On accurate computations of the Perron root*, SIAM J. Matrix Anal. Appl.**14**(1993), no. 2, 456–467. MR**1211800**, DOI 10.1137/0614032 - Egbert Falkenberg,
*On the asymptotic behaviour of the stationary distribution of Markov chains of $M/G/1$-type*, Comm. Statist. Stochastic Models**10**(1994), no. 1, 75–97. MR**1259855**, DOI 10.1080/15326349408807289 - Gene H. Golub and Charles F. Van Loan,
*Matrix computations*, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR**1002570** - Moshe Zakai,
*Some remarks on integration with respect to weak martingales*, Two-index random processes (Paris, 1980) Lecture Notes in Math., vol. 863, Springer, Berlin, 1981, pp. 149–161. MR**630311** - Robert T. Gregory and David L. Karney,
*A collection of matrices for testing computational algorithms*, Wiley-Interscience [A division of John Wiley & Sons, Inc.], New York-London-Sydney, 1969. MR**253538** - Nicholas J. Higham,
*A survey of componentwise perturbation theory in numerical linear algebra*, Mathematics of Computation 1943–1993: a half-century of computational mathematics (Vancouver, BC, 1993) Proc. Sympos. Appl. Math., vol. 48, Amer. Math. Soc., Providence, RI, 1994, pp. 49–77. MR**1314843**, DOI 10.1090/psapm/048/1314843 - Takashi Noda,
*Note on the computation of the maximal eigenvalue of a non-negative irreducible matrix*, Numer. Math.**17**(1971), 382–386. MR**295554**, DOI 10.1007/BF01436087 - C. O’Cinneide,
*Entrywise perturbation theory and error analysis for Markov chains,*Numer. Math., 65(1993):109-120. - Colm Art O’Cinneide,
*Relative-error bounds for the $LU$ decomposition via the GTH algorithm*, Numer. Math.**73**(1996), no. 4, 507–519. MR**1393178**, DOI 10.1007/s002110050203 - C. O’Cinneide, Private communication.
- G. Robertazzi
*Computer networks and systems: queueing theory and performance evaluation*, Springer-Verlag, 1990. - 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 - Robert D. Skeel,
*Iterative refinement implies numerical stability for Gaussian elimination*, Math. Comp.**35**(1980), no. 151, 817–832. MR**572859**, DOI 10.1090/S0025-5718-1980-0572859-4 - J. H. Wilkinson,
*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**184422** - Jungong Xue and Erxiong Jiang,
*Entrywise relative perturbation theory for nonsingular $M$-matrices and applications*, BIT**35**(1995), no. 3, 417–427. MR**1430919**, DOI 10.1007/BF01732614 - Jungong Xue,
*Computing the smallest eigenvalue of an $M$-matrix*, SIAM J. Matrix Anal. Appl.**17**(1996), no. 4, 748–762. MR**1410700**, DOI 10.1137/S0895479894276953

## Bibliographic Information

**Attahiru Sule Alfa**- Affiliation: Department of Industrial and Manufacturing Systems Engineering, University of Windsor, Windsor, Ontario, Canada N9B 3P4
- Email: alfa@uwindsor.ca
**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
- Email: jxue@server.uwindsor.ca
**Qiang Ye**- Affiliation: Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506-0027
- MR Author ID: 237891
- Email: qye@ms.uky.edu
- 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 - © Copyright 2001 American Mathematical Society
- Journal: Math. Comp.
**71**(2002), 217-236 - MSC (2000): Primary 65F18, 65F05
- DOI: https://doi.org/10.1090/S0025-5718-01-01325-4
- MathSciNet review: 1862996