Accurate computation of the smallest eigenvalue of a diagonally dominant 𝑀-matrix

Alfa, Attahiru; Xue, Jungong; Ye, Qiang

doi:10.1090/S0025-5718-01-01325-4

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 PDF

Math. Comp. 71 (2002), 217-236 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 0253538
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 0184422
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