Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

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

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.


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

  • 1. A. H. AI-Mohy and N. J. Higham, A new scaling and squaring algorithm for the matrix exponential, SIAM J. Matrix Anal. Appl. 31 (2009), 970-989. MR 2538661 (2010i:15016)
  • 2. A. S. Alfa, J. Xue and Q. Ye, Accurate computation of the smallest eigenvalue of a diagonally dominant M-matrix, Math. Comp. 71 (2002), 217-236. MR 1862996 (2002h:65054)
  • 3. M. Arioli, B. Codenotti and C. Fassino, The Padé method for computing the matrix expoential, Linear Algebra Appl. 240 (1996), 111-130. MR 1387290 (98f:65016)
  • 4. M. Benzi and P. Boito, Quadrature rule-based bounds for functions of adjacency matrices, Linear Algebra Appl. 433 (2010), 637-652. MR 2653828 (2011d:65106)
  • 5. M. Benzi and G. H. Golub, Bounds for the entries of matrix functions with applications to preconditioning, BIT 39 (1999), 417-438. MR 1708693 (2000h:65047)
  • 6. B. Codenotti and C. Fassino, Error analysis of two algorithms for the computation of the matrix exponential, Calcolo 29 (1992), 1-31. MR 1219619 (94c:65057)
  • 7. L. Dieci and A. Papini, Padé approximation for the exponential of a block triangular matrix, Linear Algebra Appl. 308 (2000), 183-202. MR 1751139 (2001d:65057)
  • 8. L. Deng and J. Xue, Accurate computation of exponentials of triangular essentially non-negative matrices, Journal of Fudan University (Natural Science) 50 (2011), 78-86. MR 2841355
  • 9. J. Demmel, Applied Numerical Linear Algebra, SIAM, Philadelphia, 1997. MR 1463942 (98m:65001)
  • 10. E. Estrada and J. A. Rodríguez-Velázqez, Subgraph centrality in complex networks, Phys. Rev. E 71 (2005), article 056103. MR 2171832 (2006d:94103)
  • 11. E. Estrada, N. Hatano and J. A. Rodríguez-Velázqez, Communicability in complex networks, Phys. Rev. E 77 (2008), article 036111. MR 2495430 (2010i:91171)
  • 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. D. Gross and D. R. Miller, The randomization technique as modeling tool and solution procedure for transient Markov processes, Operations Research 32 (1984), 343-361, 1984. MR 747747 (86b:60125)
  • 16. N. J. Higham, The scaling and squaring method for the matrix exponential revisited, SIAM J. Matrix Anal. Appl. 26 (2005), 1179-1193. MR 2178217 (2006g:65066)
  • 17. N. J. Higham, Functions of Matrices, Theory and computation, SIAM, Philadelphia, 2008. MR 2396439 (2009b:15001)
  • 18. C. B. Moler and C. Van Loan, Nineteen dubious ways to compute the exponential of a matrix, SIAM Rev. 20 (1978), 807-836. MR 508383 (80c:15004)
  • 19. C. B. Moler and C. Van Loan. Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev. 45 (2003), 3-49. MR 1981253 (2004d:15012)
  • 20. I. Najfeld and T. F. Havel, Derivatives of the matrix exponential and their computation, Adv. Appl. Math. 16 (1995), 321-375. MR 1342832 (96f:65013)
  • 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. C. Van Loan, The sensitivity of the matrix exponential, SIAM J. Numer. Anal. 14 (1977), 971-981. MR 0468137 (57:7975)
  • 25. R. S. Varga, Matrix Iterative Analysis, Springer, 2000. MR 1753713 (2001g:65002)
  • 26. R. C. Ward, Numerical computation of the matrix exponential with accuracy estimate, SIAM J. Numer Anal. 14 (1977), 600-610. MR 0445806 (56:4140)
  • 27. D. J. Watts and S. H. Strogatz, Collective dynamics of `small-world' networks, Nature 393 (1998), 440-442.
  • 28. J. Xue and Q. Ye, Entrywise relative perturbation bounds for exponentials of essentially non-negative matrices, Numer. Math. 110 (2008), 393-403. MR 2430985 (2009e:65073)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65F60, 65F35, 15A12

Retrieve articles in all journals with MSC (2010): 65F60, 65F35, 15A12


Additional Information

Jungong Xue
Affiliation: School of Mathematical Science, Fudan University, Shanghai, 200433, China
Email: xuej@fudan.edu.cn

Qiang Ye
Affiliation: Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506-0027
Email: qye@ms.uky.edu

DOI: https://doi.org/10.1090/S0025-5718-2013-02677-4
Received by editor(s): September 27, 2011
Published electronically: March 13, 2013
Additional Notes: The first author’s research was supported in part by NSFC under Grant 10971036 and Laboratory of Mathematics for Nonlinear Science, Fudan University
The second author’s research was supported in part by NSF under Grant DMS-0915062
Article copyright: © Copyright 2013 American Mathematical Society

American Mathematical Society