Computing exponentials of essentially non-negative matrices entrywise to high relative accuracy

Xue, Jungong; Ye, Qiang

doi:10.1090/S0025-5718-2013-02677-4

Computing exponentials of essentially non-negative matrices entrywise to high relative accuracy
HTML articles powered by AMS MathViewer

by Jungong Xue and Qiang Ye

Math. Comp. 82 (2013), 1577-1596

DOI: https://doi.org/10.1090/S0025-5718-2013-02677-4

Published electronically: March 13, 2013

PDF | Request permission

Abstract:

A real square matrix is said to be essentially non-negative if all of its off-diagonal entries are non-negative. It has recently been shown that the exponential of an essentially non-negative matrix is determined entrywise to high relative accuracy by its entries up to a condition number intrinsic to the exponential function (Numer. Math. 110 (2008), 393–403). Thus the smaller entries of the exponential may be computed to the same relative accuracy as the bigger entries. This paper develops algorithms to compute exponentials of essentially non-negative matrices entrywise to high relative accuracy.

References

Awad H. Al-Mohy and Nicholas J. Higham, A new scaling and squaring algorithm for the matrix exponential, SIAM J. Matrix Anal. Appl. 31 (2009), no. 3, 970–989. MR 2538661, DOI 10.1137/09074721X
Attahiru Sule Alfa, Jungong Xue, and Qiang Ye, Accurate computation of the smallest eigenvalue of a diagonally dominant $M$-matrix, Math. Comp. 71 (2002), no. 237, 217–236. MR 1862996, DOI 10.1090/S0025-5718-01-01325-4
M. Arioli, B. Codenotti, and C. Fassino, The Padé method for computing the matrix exponential, Linear Algebra Appl. 240 (1996), 111–130. MR 1387290, DOI 10.1016/0024-3795(94)00190-1
Michele Benzi and Paola Boito, Quadrature rule-based bounds for functions of adjacency matrices, Linear Algebra Appl. 433 (2010), no. 3, 637–652. MR 2653828, DOI 10.1016/j.laa.2010.03.035
Michele Benzi and Gene H. Golub, Bounds for the entries of matrix functions with applications to preconditioning, BIT 39 (1999), no. 3, 417–438. MR 1708693, DOI 10.1023/A:1022362401426
B. Codenotti and C. Fassino, Error analysis of two algorithms for the computation of the matrix exponential, Calcolo 29 (1992), no. 1-2, 1–31 (1993). MR 1219619, DOI 10.1007/BF02576760
Luca Dieci and Alessandra Papini, Padé approximation for the exponential of a block triangular matrix, Linear Algebra Appl. 308 (2000), no. 1-3, 183–202. MR 1751139, DOI 10.1016/S0024-3795(00)00042-2
Li Jun Deng and Jun Gong Xue, Accurate computation of exponentials of triangular essentially nonnegative matrices, J. Fudan Univ. Nat. Sci. 50 (2011), no. 1, 78–86 (Chinese, with English and Chinese summaries). MR 2841355
James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942, DOI 10.1137/1.9781611971446
Ernesto Estrada and Juan A. Rodríguez-Velázquez, Subgraph centrality in complex networks, Phys. Rev. E (3) 71 (2005), no. 5, 056103, 9. MR 2171832, DOI 10.1103/PhysRevE.71.056103
Ernesto Estrada and Naomichi Hatano, Communicability in complex networks, Phys. Rev. E (3) 77 (2008), no. 3, 036111, 12. MR 2495430, DOI 10.1103/PhysRevE.77.036111
E. Estrada, D. J. Higham and N, Hatano, Communicability betweenness in complex networks, Phys. A 388 (2009), 764–774.
C. Fassino, Computation of Matrix Function, PhD thesis, University of Pisa, Dottorato in Informatica, 1993.
W. Grassmann, Transient solutions in Markovian queueing systems, Comput. Opns. Res. 4 (1977), 47–56.
Donald Gross and Douglas R. Miller, The randomization technique as a modeling tool and solution procedure for transient Markov processes, Oper. Res. 32 (1984), no. 2, 343–361. MR 747747, DOI 10.1287/opre.32.2.343
Nicholas J. Higham, The scaling and squaring method for the matrix exponential revisited, SIAM J. Matrix Anal. Appl. 26 (2005), no. 4, 1179–1193. MR 2178217, DOI 10.1137/04061101X
Nicholas J. Higham, Functions of matrices, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. Theory and computation. MR 2396439, DOI 10.1137/1.9780898717778
Cleve Moler and Charles Van Loan, Nineteen dubious ways to compute the exponential of a matrix, SIAM Rev. 20 (1978), no. 4, 801–836. MR 508383, DOI 10.1137/1020098
Cleve Moler and Charles Van Loan, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev. 45 (2003), no. 1, 3–49. MR 1981253, DOI 10.1137/S00361445024180
Igor Najfeld and Timothy F. Havel, Derivatives of the matrix exponential and their computation, Adv. in Appl. Math. 16 (1995), no. 3, 321–375. MR 1342832, DOI 10.1006/aama.1995.1017
B. N. Parlett and K. C. Ng, Development of an accurate algorithm for exp(Bt), Tech. Report PAM-294, Center for Pure and Applied Mathematics, University of California, Berkeley, CA, 1985.
A. V. Ramesh and K. S. Trivedi, On the Sensitivity of Transient Solution of Markov Models, Proc. 1993 ACM SIGMETRICS Conference, Santa Clara, CA, May 1993.
R. B. Sidje, Expokit: A software package for computing matrix exponentials, ACM Trans. Math. Soft. 24 (1998), 130–156.
Charles Van Loan, The sensitivity of the matrix exponential, SIAM J. Numer. Anal. 14 (1977), no. 6, 971–981. MR 468137, DOI 10.1137/0714065
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
Robert C. Ward, Numerical computation of the matrix exponential with accuracy estimate, SIAM J. Numer. Anal. 14 (1977), no. 4, 600–610. MR 445806, DOI 10.1137/0714039
D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393 (1998), 440–442.
Jungong Xue and Qiang Ye, Entrywise relative perturbation bounds for exponentials of essentially non-negative matrices, Numer. Math. 110 (2008), no. 3, 393–403. MR 2430985, DOI 10.1007/s00211-008-0167-5