×

Efficient orthogonal matrix polynomial based method for computing matrix exponential. (English) Zbl 1211.65052

Summary: The matrix exponential plays a fundamental role in the solution of differential systems which appear in different science fields. This paper presents an efficient method for computing matrix exponentials based on Hermite matrix polynomial expansions. Hermite series truncation together with scaling and squaring and the application of floating point arithmetic bounds to the intermediate results provide excellent accuracy results compared with the best acknowledged computational methods. A backward-error analysis of the approximation in exact arithmetic is given. This analysis is used to provide a theoretical estimate for the optimal scaling of matrices.
Two algorithms based on this method have been implemented as MATLAB functions. They have been compared with MATLAB functions funm and expm obtaining greater accuracy in the majority of tests. A careful cost comparison analysis with expm is provided showing that the proposed algorithms have lower maximum cost for some matrix norm intervals. Numerical tests show that the application of floating point arithmetic bounds to the intermediate results may reduce considerably computational costs, reaching in numerical tests relative higher average costs than expm of only 4.43% for the final Hermite selected order, and obtaining better accuracy results in the 77.36% of the test matrices. The MATLAB implementation of the best Hermite matrix polynomial based algorithm has been made available online.

MSC:

65F30 Other matrix algorithms (MSC2010)
15A16 Matrix exponential and similar functions of matrices
34A30 Linear ordinary differential equations and systems
65L05 Numerical methods for initial value problems involving ordinary differential equations
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Frazer, R. A.; Duncan, W. J.; Collar, A. R., Elementary Matrix and Some Applications to Dynamics and Differential Equations (1946), Macmillan: Macmillan New York · Zbl 0061.01403
[2] Hirsch, M. W.; Smale, S., Differential Equations. Differential Equations, Dynamical Systems and Linear Algebra (1974), Academic Press: Academic Press New York · Zbl 0309.34001
[3] Kailath, T., Linear Systems (1980), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0458.93025
[4] Moler, C. B.; Loan, C. V., Nineteen dubious ways to compute the exponential of a matrix, SIAM Rev., 20, 4, 801-836 (1978) · Zbl 0395.65012
[5] Smith, G. D., Numerical Solution of Partial Differential Equations: Finite Difference Methods (1985), Oxford University Press · Zbl 0576.65089
[6] Moler, C. B.; Loan, C. V., Nineteen dubious ways to compute the exponential of a matrix twenty-five years later, SIAM Rev., 45, 3-49 (2003) · Zbl 1030.65029
[7] Higham, N. J., The scaling and squaring method for the matrix exponential revisited, SIAM J. Matrix Anal. Appl., 26, 4, 1179-1193 (2005) · Zbl 1081.65037
[8] Al-Mohy, A. H.; Higham, N. J., A new scaling and squaring algorithm for the matrix exponential, SIAM J. Matrix Anal. Appl., 31, 3, 970-989 (2009) · Zbl 1194.15021
[9] Dunford, N.; Schwartz, J., Linear Operators, Part I (1957), Interscience: Interscience Publishers, New York
[10] Saks, S.; Zygmund, A., Analytic Functions (1971), Elsevier Science Publishers: Elsevier Science Publishers Amsterdam, The Netherlands · JFM 60.0243.01
[11] Defez, E.; Jódar, L., Some applications of Hermite matrix polynomials series expansions, J. Comput. Appl. Math., 99, 105-117 (1998) · Zbl 0929.33006
[12] Jódar, L.; Company, R., Hermite matrix polynomials and second order matrix differential equations, J. Approx. Theory Appl., 12, 2, 20-30 (1996) · Zbl 0858.15014
[13] Paterson, M. S.; Stockmeyer, L. J., On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM J. Comput., 2, 1, 60-66 (1973) · Zbl 0262.65033
[14] Higham, N. J., Functions of Matrices: Theory and Computation (2008), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1167.15001
[15] Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1011.65010
[16] Golub, G. H.; Loan, C. V., Matrix Computations. Matrix Computations, Johns Hopkins Studies in Math. Sci. (1996), The Johns Hopkins University Press · Zbl 0865.65009
[17] Ward, R. C., Numerical computation of the matrix exponential with accuracy estimate, SIAM J. Numer. Anal., 14, 4, 600-610 (1977) · Zbl 0363.65031
[18] Davies, P. I.; Higham, N. J., A Schur-Parlett algorithm for computing matrix functions, SIAM J. Matrix Anal. Appl., 25, 2, 464-485 (2003) · Zbl 1052.65031
[19] S. Blackford, J. Dongarra, Installation guide for LAPACK, LAPACK Working Note 411, Department of Computer Science University of Tenessee, 1999.; S. Blackford, J. Dongarra, Installation guide for LAPACK, LAPACK Working Note 411, Department of Computer Science University of Tenessee, 1999.
[20] N.J. Higham, The Test Matrix Toolbox for MATLAB, Numerical Analysis Report No. 237, Manchester Centre for Computational Mathematics, Manchester, England, December 1993.; N.J. Higham, The Test Matrix Toolbox for MATLAB, Numerical Analysis Report No. 237, Manchester Centre for Computational Mathematics, Manchester, England, December 1993.
[21] T.G. Wright, Eigtool, version 2.1, 2009. <http://web.comlab.ox.ac.uk/pseudospectra/eigtool/>; T.G. Wright, Eigtool, version 2.1, 2009. <http://web.comlab.ox.ac.uk/pseudospectra/eigtool/>
[22] Najfeld, I.; Havel, T. F., Derivatives of the matrix exponential and their computation, Adv. Appl. Math., 16, 321-375 (1995) · Zbl 0839.15004
[23] Kenney, C. S.; Laub, A. J., A Schur-Fréchet algorithm for computing the logarithm and exponential of a matrix, SIAM J. Matrix Anal. Appl., 19, 3, 640-663 (1998) · Zbl 0913.65036
[24] Westreich, D., A practical method for computing the exponential of a matrix and its integral, Commun. Appl. Numer. Methods, 6, 375-380 (1990) · Zbl 0704.65028
[25] Lu, Y. Y., Computing a matrix function for exponential integrators, J. Comput. Appl. Math., 161, 203-216 (2003) · Zbl 1033.65028
[26] Dieci, L.; Papini, A., Padé approximation for the exponential of a block triangular matrix, Linear Algebra Appl., 308, 183-202 (2000) · Zbl 0958.65050
[27] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.