Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later

Published: 01 January 2003 Publication History

Abstract

In principle, the exponential of a matrix could be computed in many ways. Methods involving approximation theory, differential equations, the matrix eigenvalues, and the matrix characteristic polynomial have been proposed. In practice, consideration of computational stability and efficiency indicates that some of the methods are preferable to others but that none are completely satisfactory.
Most of this paper was originally published in 1978. An update, with a separate bibliography, describes a few recent developments.

References

[1]
Richard Bellman, Introduction to matrix analysis, Second edition, McGraw‐Hill Book Co., 1970xxiii+403
[2]
Chandler Davis, Explicit functional calculus, Linear Algebra and Appl., 6 (1973), 193–199
[3]
V. Faddeeva, Computational methods of linear algebra, Dover Publications Inc., 1959xi+252
[4]
George Forsythe, Michael Malcolm, Cleve Moler, Computer methods for mathematical computations, Prentice‐Hall Inc., 1977xi+259, Prentice‐Hall Series in Automatic Computation
[5]
J. Frame, Matrix functions and applications. II. Functions of a matrix, IEEE Spectrum, 1 (1964), 102–108
[6]
J. Frame, Matrix functions and applications. IV. Matrix functions and constituent matrices, IEEE Spectrum, 1 (1964), 123–131
[7]
J. Frame, Matrix functions and applications. V. Similarity reductions by rational or orthogonal matrices, IEEE Spectrum, 1 (1964), 103–109
[8]
F. R. Gantmacher, The Theory of Matrices, Vols. I and II, Chelsea, New York, 1959.
[9]
C. C. MacDuffee, The Theory of Matrices, Chelsea, New York, 1956.
[10]
L. Mirsky, An introduction to linear algebra, Oxford, at the Clarendon Press, 1955xi+433
[11]
M. Reed and B. Simon, Functional Analysis, Academic Press, New York, 1972.
[12]
R. Rinehart, The equivalence of definitions of a matric function, Amer. Math. Monthly, 62 (1955), 395–414
[13]
P. Rosenbloom, Bounds on functions of matrices, Amer. Math. Monthly, 74 (1967), 920–926
[14]
J. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965xviii+662
[15]
T. M. Apostol, Some explicit formulas for the matrix exponential, Amer. Math. Monthly, 76 (1969), pp. 284–292.
[16]
R. Atherton, A. DeGance, On evaluation of the derivative of the matrix exponential function, IEEE Trans. Automatic Control, AC‐20 (1975), 707–708
[17]
A. Bradshaw, The eigenstructure of sampled‐data systems with confluent eigenvalues, Internat. J. Systems Sci., 5 (1974), 607–613
[18]
Richard Bellman, Perturbation techniques in mathematics, physics, and engineering, Holt, 1964viii+118
[19]
J. C. Cavendish, On the norm of a matrix exponential, SIAM Rev., 17 (1975), pp. 174–175.
[20]
C. Cullen, Remarks on computing eAt, IEEE Trans. Automatic Control, AC‐16 (1971), 94–95
[21]
F. Fer, Résolution de l’équation matricielle dU/dt=pU par produit infini d’exponentielles matricielles, Acad. Roy. Belg. Bull. Cl. Sci. (5), 44 (1958), 818–829
[22]
Edward Fulmer, Computation of the matrix exponential, Amer. Math. Monthly, 82 (1975), 156–159
[23]
Bo Kágström, Bounds and perturbation bounds for the matrix exponential, Nordisk Tidskr. Informationsbehandling (BIT), 17 (1977), 39–57
[24]
Tosio Kato, Perturbation theory for linear operators, Die Grundlehren der mathematischen Wissenschaften, Band 132, Springer‐Verlag New York, Inc., New York, 1966xix+592
[25]
R. Kirchner, An explicit formula for eAt, Amer. Math. Monthly, 74 (1967), 1200–1204
[26]
Heinz‐Otto Kreiss, Über Matrizen die beschränkte Halbgruppen erzeugen, Math. Scand., 7 (1959), 71–80
[27]
David Powers, On the eigenstructure of the matrix exponential, Internat. J. Systems Sci., 7 (1976), 723–725
[28]
E. Putzer, Avoiding the Jordan canonical form in the discussion of linear systems with constant coefficients, Amer. Math. Monthly, 73 (1966), 2–7
[29]
N. M. Rice, More Explicit Formulas for the Exponential Matrix, Queen’s Mathematical Reprints 1970–21, Queen’s University, Kingston, ON, Canada, 1970.
[30]
H. Trotter, On the product of semi‐groups of operators, Proc. Amer. Math. Soc., 10 (1959), 545–551
[31]
C. F. Van Loan, A Study of the Matrix Exponential, Numerical Analysis Report 7, Department of Mathematics, University of Manchester, Manchester, UK, 1975.
[32]
Charles Van Loan, The sensitivity of the matrix exponential, SIAM J. Numer. Anal., 14 (1977), 971–981
[33]
G. Weiss, A. Maradudin, The Baker‐Hausdorff formula and a problem in crystal physics, J. Mathematical Phys., 3 (1962), 771–777
[34]
Allen Ziebur, On determining the structure of A by analyzing eAt, SIAM Rev., 12 (1970), 98–102
[35]
W. A. Coppel, Stability and Asymptotic Behavior of Differential Equations, D. C. Heath, Boston, 1965.
[36]
Germund Dahlquist, Stability and error bounds in the numerical integration of ordinary differential equations, Kungl. Tekn. Högsk. Handl. Stockholm. No., 130 (1959), 87–0
[37]
Charles Desoer, Hiromasa Haneda, The measure of a matrix as a tool to analyze computer algorithms for circuit analysis, IEEE Trans. Circuit Theory, CT‐19 (1972), 480–486
[38]
Emeric Deutsch, On matrix norms and logarithmic norms, Numer. Math., 24 (1975), 49–51
[39]
C. Pao, Logarithmic derivates of a square matrix, Linear Algebra and Appl., 6 (1973), 159–164
[40]
C. Pao, A further remark on the logarithmic derivatives of a square matrix, Linear Algebra and Appl., 7 (1973), 275–278
[41]
T. Ström, Minimization of norms and logarithmic norms by diagonal similarities, Computing (Arch. Elektron. Rechnen), 10 (1972), 1–7
[42]
Torsten Ström, On logarithmic norms, SIAM J. Numer. Anal., 12 (1975), 741–753
[43]
M. Healey, Study of methods of computing transition matrices, Proc. IEEE, 120 (1973), pp. 905–912.
[44]
Cleve Moler, Difficulties on computing the exponential of a matrix, AFIPS Press, Montvale, N.J., 1975, 79–82
[45]
L. Y. Bahar and A. K. Sinha, Matrix exponential approach to dynamic response, Comput. & Structures, 5 (1975), pp. 159–165.
[46]
T. A. Bickart, Matrix exponential: Approximation by truncated power series, Proc. IEEE, 56 (1968), pp. 372–373.
[47]
G. Bierman, Power series evaluation of transition and covariance matrices, IEEE Trans. Automatic Control, AC‐17 (1972), 228–232
[48]
D. A. Calahan, Numerical solution of linear systems with widely separated time constants, Proc. IEEE, 55 (1967), pp. 2016–2017.
[49]
K. C. Daly, Evaluating the matrix exponential, Electron. Lett., 8 (1972), p. 390.
[50]
W. Everling, On the evaluation of eAt by power series, Proc. IEEE, 55 (1967), p. 413.
[51]
D. A. Gall, The solution of linear constant coefficient ordinary differential equations with APL, Comput. Methods Mechanics and Engrg., 1 (1972), pp. 189–196.
[52]
M. L. Liou, A novel method of evaluating transient response, Proc. IEEE, 54 (1966), pp. 20–23.
[53]
J. B. Mankin and J. C. Hung, On Roundoff Errors in Computation of Transition Matrices, Reprints of the Joint Automatic Control Conference, University of Colorado, Boulder, CO, 1969, pp. 60–64.
[54]
E. J. Mastascusa, A relation between Liou’s method and fourth order Runge–Kutta method for evaluation of transient response, Proc. IEEE, 57 (1969), pp. 803–804.
[55]
J. B. Plant, On the computation of transient matrices for time invariant systems, Proc. IEEE, 56 (1968), pp. 1397–1398.
[56]
M. M. Shah, On the Evaluation of eAt, Cambridge Report CUED/B‐Control TR8, Cambridge University, Cambridge, UK, 1971.
[57]
M. M. Shah, Analysis of Roundoff and Truncation Errors in the Computation of Transition Matrices, Cambridge Report CUED/B‐Control TR12, Cambridge University, Cambridge, UK, 1971.
[58]
C. Standish, Truncated Taylor series approximation to the state transition matrix of a continuous parameter finite Markov chain, Linear Algebra and Appl., 12 (1975), 179–183
[59]
D. E. Whitney, Propagated error bounds for numerical solution of transient response, Proc. IEEE, 54 (1966), pp. 1084–1085.
[60]
D. E. Whitney, More similarities between Runge–Kutta and matrix exponential methods for evaluating transient response, Proc. IEEE, 57 (1969), pp. 2053–2054.
Rational approximation.
[61]
James Blue, Hermann Gummel, Rational approximations to matrix exponential for systems of stiff differential equations, J. Computational Phys., 5 (1970), 70–83
[62]
W. Cody, G. Meinardus, R. Varga, Chebyshev rational approximations to e-x in [0,+) and applications to heat‐conduction problems, J. Approximation Theory, 2 (1969), 50–65
[63]
Wyman Fair, Yudell Luke, Padé approximations to the operator exponential, Numer. Math., 14 (1969/1970), 379–382
[64]
Syvert Nørsett, C‐polynomials for rational approximation to the exponential function, Numer. Math., 25 (1975/76), 39–56
[65]
E. Saff, On the degree of best rational approximation to the exponential function, J. Approximation Theory, 9 (1973), 97–101
[66]
E. Saff, R. Varga, On the zeros and poles of Padé approximants to ez, Numer. Math., 25 (1975/76), 1–14
[67]
R. E. Scraton, Comment on rational approximants to the matrix exponential, Electron. Lett., 7 (1971), pp. 260–261.
[68]
J. Siemieniuch, Properties of certain rational approximations to ez, Nordisk Tidskr. Informationsbehandling (BIT), 16 (1976), 172–191
[69]
G. Siemieniuch and I. Gladwell, On Time Discretizations for Linear Time Dependent Partial Differential Equations, Numerical Analysis Report 5, Department of Mathematics, University of Manchester, Manchester, UK, 1974.
[70]
D. Trujillo, The direct numerical integration of linear matrix differential equations using Padé approximations, Internat. J. Numer. Methods Engrg., 9 (1975), 259–270
[71]
Richard Varga, On higher order stable implicit methods for solving parabolic partial differential equations, J. Math. and Phys., 40 (1961), 220–231
[72]
R. C. Ward, Numerical computation of the matrix exponential with accuracy estimate, SIAM J. Numer. Anal., 14 (1977), pp. 600–610.
[73]
A. Wragg and C. Davies, Evaluation of the matrix exponential, Electron. Lett., 9 (1973), pp. 525–526.
[74]
A. Wragg, C. Davies, Computation of the exponential of a matrix. I. Theoretical considerations, J. Inst. Math. Appl., 11 (1973), 369–375
[75]
A. Wragg, C. Davies, Computation of the exponential of a matrix. II. Practical considerations, J. Inst. Math. Appl., 15 (1975), 273–278
[76]
V. Zakian, Rational approximants to the matrix exponential, Electron. Lett., 6 (1970), pp. 814–815.
[77]
V. Zakian and R. E. Scraton, Comments on rational approximations to the matrix exponential, Electron. Lett., 7 (1971), pp. 260–262.
Polynomial methods.
[78]
G. J. Bierman, Finite series solutions for the transition matrix and covariance of a time‐invariant system, IEEE Trans. Automat. Control, AC‐16 (1971), pp. 173–175.
[79]
J. A. Boehm and J. A. Thurman, An algorithm for generating constituent matrices, IEEE Trans. Circuit Theory, CT‐18 (1971), pp. 178–179.
[80]
C. F. Chen and R. R. Parker, Generalization of Heaviside’s expansion technique to transition matrix evaluation, IEEE Trans. Educ., E‐9 (1966), pp. 209–212.
[81]
W. C. Davidon, Exponential Function of a 2‐by‐2 Matrix, Hewlett‐Packard HP65 Library Program.
[82]
S. Deards, On the evaluation of exp(tA), Matrix Tensor Quart., 23 (1973), pp. 141–142.
[83]
S. Ganapathy and R. S. Rao, Transient response evaluation from the state transition matrix, Proc. IEEE, 57 (1969), pp. 347–349.
[84]
İzzet Göknar, On the evaluation of constituent matrices, Internat. J. Systems Sci., 5 (1974), 213–218
[85]
Ignace Kolodner, On exp(tA) with A satisfying a polynomial, J. Math. Anal. Appl., 52 (1975), 514–524
[86]
Y. L. Kuo and M. L. Liou, Comments on “A novel method of evaluating eAt in closed form,” IEEE Trans. Automat. Control, AC‐16 (1971), p. 521.
[87]
E. J. Mastascusa, A method of calculating eAt based on the Cayley–Hamilton theorem, Proc. IEEE, 57 (1969), pp. 1328–1329.
[88]
K. R. Rao and N. Ahmed, Heaviside expansion of transition matrices, Proc. IEEE, 56 (1968), pp. 884–886.
[89]
K. R. Rao and N. Ahmed, Evaluation of transition matrices, IEEE Trans. Automat. Control, AC‐14 (1969), pp. 779–780.
[90]
B. Roy, A. K. Mandal, D. Roy Choudhury, and A. K. Choudhury, On the evaluation of the state transition matrix, Proc. IEEE, 57 (1969), pp. 234–235.
[91]
M. N. S. Swamy, On a formula for evaluating eAt when the eigenvalues are not necessarily distinct, Matrix Tensor Quart., 23 (1972), pp. 67–72.
[92]
Mathukumalli Vidyasagar, A novel method of evaluating eAt in closed form, IEEE Trans. Automatic Control, AC‐15 (1970), 600–601
[93]
V. Zakian, Solution of homogeneous ordinary linear differential systems by numerical inversion of Laplace transforms, Electron. Lett., 7 (1971), 546–548
[94]
A. K. Choudhury, D. R. Choudhury, B. Roy, and A. K. Mandal, On the evaluation of eAt, Proc. IEEE, 56 (1968), pp. 1110–1111.
[95]
L. Falcidieno and A. Luvinson, A Numerical Approach to Computing the Companion Matrix Exponential, CSELT technical report 4, 1975, pp. 69–71.
[96]
C. Harris, Evaluation of matrix polynomials in the state companion matrix of linear time invariant systems, Internat. J. Systems Sci., 4 (1973), 301–307
[97]
D. W. Kammler, Numerical Evaluation of exp(At) When A is a Companion Matrix, manuscript, University of Southern Illinois, Carbondale, IL, 1976.
[98]
I. Kaufman, Evaluation of an analytical function of a companion matrix with distinct eigenvalues, Proc. IEEE, 57 (1969), 1180–1181
[99]
I. Kaufman, A note on the “Evaluation of an analytical function of a companion matrix with distinct eigenvalues,” Proc. IEEE, 57 (1969), pp. 2083–2084.
[100]
I. Kaufman and P. H. Roe, On systems described by a companion matrix, IEEE Trans. Automat. Control, AC‐15 (1970), pp. 692–693.
[101]
I. Kaufman, H. Mann, and J. Vlach, A fast procedure for the analysis of linear time invariant networks, IEEE Trans. Circuit Theory, CT‐18 (1971), pp. 739–741.
[102]
M. L. Liou, Evaluation of the transition matrix, Proc. IEEE, 55 (1967), pp. 228–229.
[103]
A. K. Mandal, et al., Numerical computation method for the evaluation of the transition matrix, Proc. IEEE, 116 (1969), pp. 500–502.
[104]
W. E. Thomson, Evaluation of transient response, Proc. IEEE, 54 (1966), p. 1584.
Ordinary differential equations.
[105]
B. Ehle, J. Lawson, Generalized Runge‐Kutta processes for stiff initial‐value problems, J. Inst. Math. Appl., 16 (1975), 11–21
[106]
C. W. Gear, Numerical Initial Value Problems in Ordinary Differential Equations, Prentice–Hall, Englewood Cliffs, NJ, 1971.
[107]
L. Shampine, M. Gordon, Computer solution of ordinary differential equations, W. H. Freeman and Co., 1975x+318, The initial value problem
[108]
L. F. Shampine and H. A. Watts, Practical Solution of Ordinary Differential Equations by Runge–Kutta Methods, Sandia Lab Report SAND 76‐0585, Albuquerque, NM, 1976.
[109]
J. Starner, Numerical Solution of Implicit Differential‐Algebraic Equations, Ph.D. Thesis, University of New Mexico, Albuquerque, NM, 1976.
Matrix decomposition methods.
[110]
G. Golub, J. Wilkinson, Ill‐conditioned eigensystems and the computation of the Jordan canonical form, SIAM Rev., 18 (1976), 578–619
[111]
Bo Ka˙gström, Axel Ruhe, An algorithm for numerical computation of the Jordan normal form of a complex matrix, ACM Trans. Math. Software, 6 (1980), 398–419
[112]
B. Parlett, A recurrence among the elements of functions of triangular matrices, Linear Algebra and Appl., 14 (1976), 117–121
[113]
B. T. Smith, J. M. Boyle, J. J. Dongarra, B. S. Garbow, Y. Ikebe, V. C. Klema, and C. B. Moler, Matrix Eigensystem Routines: EISPACK Guide, 2nd ed., Lecture Notes in Comput. Sci. 6, Springer‐Verlag, New York, 1976.
Integrals involving eAt.
[114]
E. S. Armstrong and A. K. Caglayan, An Algorithm for the Weighting Matrices in the Sampled‐Data Optimal Linear Regulator Problem, NASA technical note, TN D‐8372, 1976.
[115]
J. Johnson and C. L. Phillips, An algorithm for the computation of the integral of the state transition matrix, IEEE Trans. Automat. Control, AC‐16 (1971), pp. 204–205.
[116]
C. Kallstrom, Computing exp(A) and exp(As)ds, Report 7309, Division of Automatic Control, Lund Institute of Technology, Lund, Sweden, 1973.
[117]
Alexander Levis, Some computational aspects of the matrix exponential, IEEE Trans. Automatic Control, AC‐14 (1969), 410–411
[118]
Charles Van Loan, Computing integrals involving the matrix exponential, IEEE Trans. Automat. Control, 23 (1978), 395–404
[119]
F. H. Branin, Computer methods of network analysis, Proc. IEEE, 55 (1967), pp. 1787–1801.
[120]
R. Brockett, Finite Dimensional Linear Systems, John Wiley, New York, 1970.
[121]
K. F. Hansen, B. V. Koen, and W. W. Little, Stable numerical solutions of the reactor kinetics equations, Nuclear Sci. Engrg., 22 (1965), pp. 51–59.
[122]
J. A. W. da Nobrega, A new solution of the point kinetics equations, Nuclear Sci. Engrg., 46 (1971), pp. 366–375.

Cited By

View all
  • (2024)Generating Hidden Markov Models from Process Models Through Nonnegative Tensor FactorizationACM Transactions on Modeling and Computer Simulation10.1145/366481334:4(1-19)Online publication date: 12-Jul-2024
  • (2024)A Generalized Nyquist-Shannon Sampling Theorem Using the Koopman OperatorIEEE Transactions on Signal Processing10.1109/TSP.2024.343661072(3595-3610)Online publication date: 1-Jan-2024
  • (2024)A multi-direction guided mutation-driven stable swarm intelligence algorithm with translation and rotation invariance for global optimizationApplied Soft Computing10.1016/j.asoc.2024.111614159:COnline publication date: 1-Jul-2024
  • Show More Cited By

Index Terms

  1. Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
    Index terms have been assigned to the content through auto-classification.

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image SIAM Review
    SIAM Review  Volume 45, Issue 1
    2003
    156 pages
    ISSN:0036-1445
    DOI:10.1137/siread.2003.45.issue-1
    Issue’s Table of Contents

    Publisher

    Society for Industrial and Applied Mathematics

    United States

    Publication History

    Published: 01 January 2003

    Author Tags

    1. 15A15
    2. 65F15
    3. 65F30
    4. 65L99

    Author Tags

    1. matrix
    2. exponential
    3. roundoff error
    4. truncation error
    5. condition

    Qualifiers

    • Research-article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 22 Nov 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Generating Hidden Markov Models from Process Models Through Nonnegative Tensor FactorizationACM Transactions on Modeling and Computer Simulation10.1145/366481334:4(1-19)Online publication date: 12-Jul-2024
    • (2024)A Generalized Nyquist-Shannon Sampling Theorem Using the Koopman OperatorIEEE Transactions on Signal Processing10.1109/TSP.2024.343661072(3595-3610)Online publication date: 1-Jan-2024
    • (2024)A multi-direction guided mutation-driven stable swarm intelligence algorithm with translation and rotation invariance for global optimizationApplied Soft Computing10.1016/j.asoc.2024.111614159:COnline publication date: 1-Jul-2024
    • (2024)Stability analysis of explicit exponential Rosenbrock methods for stiff differential equations with constant delayApplied Mathematics and Computation10.1016/j.amc.2024.128978482:COnline publication date: 1-Dec-2024
    • (2024)The constant solution method for solving large-scale differential Sylvester matrix equations with time invariant coefficientsNumerical Algorithms10.1007/s11075-023-01653-396:1(449-488)Online publication date: 1-May-2024
    • (2024)An Explicit Exponential Integrator Based on Faber Polynomials and its Application to Seismic Wave ModelingJournal of Scientific Computing10.1007/s10915-023-02413-098:2Online publication date: 3-Jan-2024
    • (2024)Lamb waves in stratified plates: appearance of “forbidden” phase velocitiesZeitschrift für Angewandte Mathematik und Physik (ZAMP)10.1007/s00033-024-02245-475:3Online publication date: 9-May-2024
    • (2024)Synchronous Diffusion for Unsupervised Smooth Non-rigid 3D Shape MatchingComputer Vision – ECCV 202410.1007/978-3-031-72652-1_16(262-281)Online publication date: 29-Sep-2024
    • (2024)Uncovering Dynamic Structures Within Cyclic Attractors of Asynchronous Boolean Networks with Spectral ClusteringComputational Methods in Systems Biology10.1007/978-3-031-71671-3_16(226-246)Online publication date: 17-Sep-2024
    • (2024)Solving Maximum Cut Problem with Multi-objective Enhance Quantum Approximate Optimization AlgorithmComputational Science and Its Applications – ICCSA 2024 Workshops10.1007/978-3-031-65343-8_16(244-252)Online publication date: 1-Jul-2024
    • Show More Cited By

    View Options

    View options

    Login options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media