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

Authors: Jungong Xue and Qiang Ye
Journal: Math. Comp. 82 (2013), 1577-1596
MSC (2010): Primary 65F60; Secondary 65F35, 15A12
DOI: https://doi.org/10.1090/S0025-5718-2013-02677-4
Published electronically: March 13, 2013
MathSciNet review: 3042576
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

1. 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, https://doi.org/10.1137/09074721X
2. Attahiru Sule Alfa, Jungong Xue, and Qiang Ye, Accurate computation of the smallest eigenvalue of a diagonally dominant 𝑀-matrix, Math. Comp. 71 (2002), no. 237, 217–236. MR 1862996, https://doi.org/10.1090/S0025-5718-01-01325-4
3. M. Arioli, B. Codenotti, and C. Fassino, The Padé method for computing the matrix exponential, Linear Algebra Appl. 240 (1996), 111–130. MR 1387290, https://doi.org/10.1016/0024-3795(94)00190-1
4. 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, https://doi.org/10.1016/j.laa.2010.03.035
5. 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, https://doi.org/10.1023/A:1022362401426
6. 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, https://doi.org/10.1007/BF02576760
7. 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, https://doi.org/10.1016/S0024-3795(00)00042-2
8. 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
9. James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942
10. 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, https://doi.org/10.1103/PhysRevE.71.056103
11. Ernesto Estrada and Naomichi Hatano, Communicability in complex networks, Phys. Rev. E (3) 77 (2008), no. 3, 036111, 12. MR 2495430, https://doi.org/10.1103/PhysRevE.77.036111
12. E. Estrada, D. J. Higham and N, Hatano, Communicability betweenness in complex networks, Phys. A 388 (2009), 764-774.
13. C. Fassino, Computation of Matrix Function, PhD thesis, University of Pisa, Dottorato in Informatica, 1993.
14. W. Grassmann, Transient solutions in Markovian queueing systems, Comput. Opns. Res. 4 (1977), 47-56.
15. 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, https://doi.org/10.1287/opre.32.2.343
16. 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, https://doi.org/10.1137/04061101X
17. Nicholas J. Higham, Functions of matrices, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. Theory and computation. MR 2396439
18. 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, https://doi.org/10.1137/1020098
19. 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, https://doi.org/10.1137/S00361445024180
20. 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, https://doi.org/10.1006/aama.1995.1017
21. 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.
22. 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.
23. R. B. Sidje, Expokit: A software package for computing matrix exponentials, ACM Trans. Math. Soft. 24 (1998), 130-156.
24. Charles Van Loan, The sensitivity of the matrix exponential, SIAM J. Numer. Anal. 14 (1977), no. 6, 971–981. MR 468137, https://doi.org/10.1137/0714065
25. Richard S. Varga, Matrix iterative analysis, Second revised and expanded edition, Springer Series in Computational Mathematics, vol. 27, Springer-Verlag, Berlin, 2000. MR 1753713
26. Robert C. Ward, Numerical computation of the matrix exponential with accuracy estimate, SIAM J. Numer. Anal. 14 (1977), no. 4, 600–610. MR 445806, https://doi.org/10.1137/0714039
27. D. J. Watts and S. H. Strogatz, Collective dynamics of `small-world' networks, Nature 393 (1998), 440-442.
28. 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, https://doi.org/10.1007/s00211-008-0167-5