Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-23T00:23:18.781Z Has data issue: false hasContentIssue false
  • English
  • Français

Computing matrix functions

Published online by Cambridge University Press:  10 May 2010

Nicholas J. Higham  and
Awad H. Al-Mohy
Nicholas J. Higham
Affiliation:
School of Mathematics, University of Manchester, Manchester, M13 9PL, UK E-mail: [email protected], [email protected]
Awad H. Al-Mohy
Affiliation:
School of Mathematics, University of Manchester, Manchester, M13 9PL, UK E-mail: [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

The need to evaluate a function f(A) ∈ ℂn×n of a matrix A ∈ ℂn×n arises in a wide and growing number of applications, ranging from the numerical solution of differential equations to measures of the complexity of networks. We give a survey of numerical methods for evaluating matrix functions, along with a brief treatment of the underlying theory and a description of two recent applications. The survey is organized by classes of methods, which are broadly those based on similarity transformations, those employing approximation by polynomial or rational functions, and matrix iterations. Computation of the Fréchet derivative, which is important for condition number estimation, is also treated, along with the problem of computing f(A)b without computing f(A). A summary of available software completes the survey.

Type
Research Article
Information
Acta Numerica , Volume 19 , May 2010 , pp. 159 - 208
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Afanasjew, M., Eiermann, M., Ernst, O. G. and Güttel, S. (2008), ‘Implementation of a restarted Krylov subspace method for the evaluation of matrix functions’, Linear Algebra Appl. 429, 2293–2314.CrossRefGoogle Scholar
Al-Mohy, A. H. and Higham, N. J. (2009 a), ‘Computing the Fréchet derivative of the matrix exponential, with an application to condition number estimation’, SIAM J. Matrix Anal. Appl. 30, 1639–1657.CrossRefGoogle Scholar
Al-Mohy, A. H. and Higham, N. J. (2009 b), ‘A new scaling and squaring algorithm for the matrix exponential’, SIAM J. Matrix Anal. Appl. 31, 970–989.CrossRefGoogle Scholar
Al-Mohy, A. H. and Higham, N. J. (2010), ‘The complex step approximation to the Fréchet derivative of a matrix function’, Numer. Algorithms 53, 133–148.CrossRefGoogle Scholar
Antoulas, A. C. (2005), Approximation of Large-Scale Dynamical Systems, SIAM, Philadelphia, PA, USA.CrossRefGoogle Scholar
Arioli, M. and Loghin, D. (2009), ‘Discrete interpolation norms with applications’, SIAM J. Numer. Anal. 47, 2924–2951.CrossRefGoogle Scholar
Baker, G. A. Jr, and Graves-Morris, P. (1996), Padé Approximants, Vol. 59 of Encyclopedia of Mathematics and its Applications, second edn, Cambridge University Press, Cambridge, UK.Google Scholar
Barraud, A. Y. (1979), ‘Investigations autour de la fonction signe d‘une matrice application a l'équation de Riccati’, RAIRO Automatique/Systems Analysis and Control 13, 335–368.Google Scholar
Bavely, C. A. and Stewart, G. W. (1979), ‘An algorithm for computing reducing subspaces by block diagonalization’, SIAM J. Numer. Anal. 16, 359–367.CrossRefGoogle Scholar
Berland, H., Skaflestad, B. and Wright, W. (2007), ‘EXPINT: A MATLAB package for exponential integrators’, ACM Trans. Math. Software 33, #4.CrossRefGoogle Scholar
Bini, D. A., Higham, N. J. and Meini, B. (2005), ‘Algorithms for the matrix pth root’, Numer. Algorithms 39, 349–378.CrossRefGoogle Scholar
Björck, Å. and Hammarling, S. (1983), ‘A Schur method for the square root of a matrix’, Linear Algebra Appl. 52/53, 127–140.CrossRefGoogle Scholar
Bradford, R. J., Corless, R. M., Davenport, J. H., Jeffrey, D. J. and Watt, S. M. (2002), ‘Reasoning about the elementary functions of complex analysis’, Annals of Mathematics and Artificial Intelligence 36, 303–318.CrossRefGoogle Scholar
Brezinski, C. and Van Iseghem, J. (1995), A taste of Padé approximation. In Acta Numerica, Vol. 4, Cambridge University Press, pp. 53–103.Google Scholar
Cayley, A. (1858), ‘A memoir on the theory of matrices’, Philos. Trans. Roy. Soc. London 148, 17–37.Google Scholar
Charitos, T., de Waal, P. R. and van der Gaag, L. C. (2008), ‘Computing short-interval transition matrices of a discrete-time Markov chain from partially observed data’, Statistics in Medicine 27, 905–921.CrossRefGoogle ScholarPubMed
Cheng, S. H., Higham, N. J., Kenney, C. S. and Laub, A. J. (2000), Return to the middle ages: A half-angle iteration for the logarithm of a unitary matrix. In Proc. 14th International Symposium of Mathematical Theory of Networks and Systems, Perpignan, France. CD ROM.Google Scholar
Cheng, S. H., Higham, N. J., Kenney, C. S. and Laub, A. J. (2001), ‘Approximating the logarithm of a matrix to specified accuracy’, SIAM J. Matrix Anal. Appl. 22, 1112–1125.CrossRefGoogle Scholar
Collar, A. R. (1978), ‘The first fifty years of aeroelasticity’, Aerospace (Royal Aeronautical Society Journal) 5, 12–20.Google Scholar
Cox, M. G. and Harris, P. M. (2004), Numerical analysis for algorithm design in metrology, Software Support for Metrology Best Practice Guide No. 11, National Physical Laboratory, Teddington, UK.Google Scholar
Crofts, J. J. and Higham, D. J. (2009), ‘A weighted communicability measure applied to complex brain networks’, J. Roy. Soc. Interface 6, 411–414.CrossRefGoogle ScholarPubMed
Davies, P. I. and Higham, N. J. (2003), ‘A Schur-Parlett algorithm for computing matrix functions’, SIAM J. Matrix Anal. Appl. 25, 464–485.CrossRefGoogle Scholar
Davies, P. I. and Higham, N. J. (2005), Computing f(A)b for matrix functions f. In QCD and Numerical Analysis III (Boriçi, A., Frommer, A., Joó, B., Kennedy, A. and Pendleton, B., eds), Vol. 47 of Lecture Notes in Computational Science and Engineering, Springer, Berlin, pp. 15–24.CrossRefGoogle Scholar
Davis, C. (1973), ‘Explicit functional calculus’, Linear Algebra Appl. 6, 193–199.CrossRefGoogle Scholar
Denman, E. D. and Beavers, A. N. Jr, (1976), ‘The matrix sign function and computations in systems’, Appl. Math. Comput. 2, 63–94.CrossRefGoogle Scholar
Descloux, J. (1963), ‘Bounds for the spectral norm of functions of matrices’, Numer. Math. 15, 185–190.CrossRefGoogle Scholar
Dieci, L. and Papini, A. (2000), ‘Padé approximation for the exponential of a block triangular matrix’, Linear Algebra Appl. 308, 183–202.CrossRefGoogle Scholar
Dieci, L., Morini, B. and Papini, A. (1996), ‘Computational techniques for real logarithms of matrices’, SIAM J. Matrix Anal. Appl. 17, 570–593.CrossRefGoogle Scholar
Elsner, L. (1970), ‘Iterative Verfahren zur Lösung der Matrizengleichung X 2 - A = 0’, Buletinul Institutului Politehnic din Iasi xvi, 15–24.Google Scholar
Estrada, E. and Hatano, N. (2008), ‘Communicability in complex networks’, Phys. Review E 77, 036111.CrossRefGoogle ScholarPubMed
Estrada, E. and Higham, D. J. (2008), Network properties revealed through matrix functions. Mathematics Research Report 17, University of Strathclyde, Scotland, UK. To appear in SIAM Rev.Google Scholar
Estrada, E. and Rodríguez-Velázquez, J. A. (2005 a), ‘Spectral measures of bipartivity in complex networks’, Phys. Review E 72, 046105.CrossRefGoogle ScholarPubMed
Estrada, E. and Rodríguez-Velázquez, J. A. (2005 b), ‘Subgraph centrality in complex networks’, Phys. Review E 71, 056103.CrossRefGoogle ScholarPubMed
Estrada, E., Higham, D. J. and Hatano, N. (2009), ‘Communicability betweenness in complex networks’, Physica A 388, 764–774.CrossRefGoogle Scholar
Fiori, S. (2008), ‘Leap-frog-type learning algorithms over the Lie group of unitary matrices’, Neurocomputing 71, 2224–2244.CrossRefGoogle Scholar
Frazer, R. A., Duncan, W. J. and Collar, A. R. (1938), Elementary Matrices and Some Applications to Dynamics and Differential Equations, Cambridge University Press, Cambridge, UK. 1963 printing.CrossRefGoogle Scholar
Frommer, A. and Simoncini, V. (2008 a), Matrix functions. In Model Order Reduction: Theory, Research Aspects and Applications (Schilders, W. H. A., van der Vorst, H. A. and Rommes, J., eds), Springer, Berlin, pp. 275–303.CrossRefGoogle Scholar
Frommer, A. and Simoncini, V. (2008 b), ‘Stopping criteria for rational matrix functions of Hermitian and symmetric matrices’, SIAM J. Sci. Comput. 30, 1387–1412.CrossRefGoogle Scholar
Gantmacher, F. R. (1959), The Theory of Matrices, Vol. one, Chelsea, New York.Google Scholar
Giles, M. B., Duta, M. C., Müller, J.-D. and Pierce, N. A. (2003), ‘Algorithm developments for discrete adjoint methods’, AIAA Journal 4, 198–205.CrossRefGoogle Scholar
Goldstine, H. H. (1977), A History of Numerical Analysis from the 16th through the 19th Century, Springer, New York.CrossRefGoogle Scholar
Golub, G. H. and Van Loan, C. F. (1996), Matrix Computations, third edn, Johns Hopkins University Press, Baltimore, MD, USA.Google Scholar
Greco, F. and Iannazzo, B. (2010), ‘A binary powering algorithm for computing primary matrix roots’, Numer. Algorithms. To appear.CrossRefGoogle Scholar
Grimm, V. and Hochbruck, M. (2008), ‘Rational approximation to trigonometric operator’, BIT 48, 215–229.CrossRefGoogle Scholar
Guo, C.-H. (2009), ‘On Newton's method and Halley's method for the principal pth root of a matrix’, Linear Algebra Appl. 432, 1905–1922.CrossRefGoogle Scholar
Guo, C.-H. and Higham, N. J. (2006), ‘A Schur-Newton method for the matrix pth root and its inverse’, SIAM J. Matrix Anal. Appl. 28, 788–804.CrossRefGoogle Scholar
Hale, N., Higham, N. J. and Trefethen, L. N. (2008), ‘Computing Aα, log(A) and related matrix functions by contour integrals’, SIAM J. Numer. Anal. 46, 2505–2523.CrossRefGoogle Scholar
Hargreaves, G. (2005), Topics in matrix computations: Stability and efficiency of algorithms. PhD thesis, University of Manchester, Manchester, England.Google Scholar
Hargreaves, G. I. and Higham, N. J. (2005), ‘Efficient algorithms for the matrix cosine and sine’, Numer. Algorithms 40, 383–400.CrossRefGoogle Scholar
Higham, N. J. (1986 a), ‘Computing the polar decomposition: With applications’, SIAM J. Sci. Statist. Comput. 7, 1160–1174.CrossRefGoogle Scholar
Higham, N. J. (1986 b), ‘Newton‘s method for the matrix square root’, Math. Comp. 46, 537–549.Google Scholar
Higham, N. J. (1987), ‘Computing real square roots of a real matrix’, Linear Algebra Appl. 88/89, 405–430.CrossRefGoogle Scholar
Higham, N. J. (1994), ‘The matrix sign decomposition and its relation to the polar decomposition’, Linear Algebra Appl. 212/213, 3–20.CrossRefGoogle Scholar
Higham, N. J. (1997), ‘Stable iterations for the matrix square root’, Numer. Algorithms 15, 227–242.CrossRefGoogle Scholar
Higham, N. J. (2001), ‘Evaluating Padé approximants of the matrix logarithm’, SIAM J. Matrix Anal. Appl. 22, 1126–1135.CrossRefGoogle Scholar
Higham, N. J. (2002), Accuracy and Stability of Numerical Algorithms, second edn, SIAM, Philadelphia, PA, USA.CrossRefGoogle Scholar
Higham, N. J. (2005), ‘The scaling and squaring method for the matrix exponential revisited’, SIAM J. Matrix Anal. Appl. 26, 1179–1193.CrossRefGoogle Scholar
Higham, N. J. (2008), Functions of Matrices: Theory and Computation, SIAM, Philadelphia, PA, USA.CrossRefGoogle Scholar
Higham, N. J. (2009), ‘The scaling and squaring method for the matrix exponential revisited’, SIAM Rev. 51, 747–764.CrossRefGoogle Scholar
Higham, N. J., ‘The Matrix Function Toolbox’. http://www.ma.man.ac.uk/~higham/mftoolbox.Google Scholar
Higham, N. J. and Lin, L. (2009), On pth roots of stochastic matrices. MIMS EPrint 2009.21, Manchester Institute for Mathematical Sciences, The University of Manchester, UK.Google Scholar
Higham, N. J. and Smith, M. I. (2003), ‘Computing the matrix cosine’, Numer. Algorithms 34, 13–26.CrossRefGoogle Scholar
Higham, N. J. and Tisseur, F. (2000), ‘A block algorithm for matrix 1-norm estimation, with an application to 1-norm pseudospectra’, SIAM J. Matrix Anal. Appl. 21, 1185–1201.CrossRefGoogle Scholar
Higham, N. J., Mackey, D. S., Mackey, N. and Tisseur, F. (2005), ‘Functions preserving matrix groups and iterations for the matrix square root’, SIAM J. Matrix Anal. Appl. 26, 849–877.CrossRefGoogle Scholar
Hochbruck, M. and Ostermann, A. (2010), Exponential integrators. In Acta Numerica, Vol. 19, Cambridge University Press, pp. 209–286.Google Scholar
Horn, R. A. and Johnson, C. R. (1991), Topics in Matrix Analysis, Cambridge University Press, Cambridge, UK.CrossRefGoogle Scholar
Iannazzo, B. (2006), ‘On the Newton method for the matrix Pth root’, SIAM J. Matrix Anal. Appl. 28, 503–523.CrossRefGoogle Scholar
Ilić, M., Turner, I. W. and Simpson, D. P. (2009), ‘A restarted Lanczos approximation to functions of a symmetric matrix’, IMA J. Numer. Anal. Advance Access published on June 17, 2009. doi: 10.1093/imanum/drp003.CrossRefGoogle Scholar
Israel, R. B., Rosenthal, J. S. and Wei, J. Z. (2001), ‘Finding generators for Markov chains via empirical transition matrices, with applications to credit ratings’, Mathematical Finance 11, 245–265.CrossRefGoogle Scholar
Jarrow, R. A., Lando, D. and Turnbull, S. M. (1997), ‘A Markov model for the term structure of credit risk spreads’, Rev. Financial Stud. 10, 481–523.CrossRefGoogle Scholar
Kahan, W. (1987), Branch cuts for complex elementary functions, or Much Ado About Nothing‘s sign bit. In The State of the Art in Numerical Analysis (Iserles, A. and Powell, M. J. D., eds), Oxford University Press, pp. 165–211.Google Scholar
Kenney, C. S. and Laub, A. J. (1989 a), ‘Condition estimates for matrix functions’, SIAM J. Matrix Anal. Appl. 10, 191–209.CrossRefGoogle Scholar
Kenney, C. S. and Laub, A. J. (1989 b), ‘Padé error estimates for the logarithm of a matrix’, Interna t. J. Control 50, 707–730.CrossRefGoogle Scholar
Kenney, C. S. and Laub, A. J. (1991 a), ‘Polar decomposition and matrix sign function condition estimates’, SIAM J. Sci. Statist. Comput. 12, 488–504.CrossRefGoogle Scholar
Kenney, C. S. and Laub, A. J. (1991 b), ‘Rational iterative methods for the matrix sign function’, SIAM J. Matrix Anal. Appl. 12, 273–291.CrossRefGoogle Scholar
Kenney, C. S. and Laub, A. J. (1998), ‘A Schur-Fréchet algorithm for computing the logarithm and exponential of a matrix’, SIAM J. Matrix Anal. Appl. 19, 640–663.CrossRefGoogle Scholar
Koikari, S. (2009), ‘Algorithm 894: On a block Schur-Parlett algorithm for φ-functions based on the sep-inverse estimate’, ACM Trans. Math. Software 36, #12.CrossRefGoogle Scholar
Kreinin, A. and Sidelnikova, M. (2001), ‘Regularization algorithms for transition matrices’, Algo Research Quarterly 4, 23–40.Google Scholar
Laasonen, P. (1958), ‘On the iterative solution of the matrix equation AX2-I = 0’, Math. Tables Aids Comp. 12, 109–116.CrossRefGoogle Scholar
Lancaster, P. and Tismenetsky, M. (1985), The Theory of Matrices, second edn, Academic Press, London.Google Scholar
Laszkiewicz, B. and Zietak, K. (2009), ‘A Padé family of iterations for the matrix sector function and the matrix pth root’, Numer. Linear Algebra Appl. 16, 951–970.CrossRefGoogle Scholar
Lavallée, P.-F., Malyshev, A. and Sadkane, M. (1997), Spectral portrait of matrices by block diagonalization. In Numerical Analysis and its Applications (Vulkov, L., Waśniewski, J. and Yalamov, P., eds), Vol. 1196 of Lecture Notes in Computer Science, Springer, Berlin, pp. 266–273.CrossRefGoogle Scholar
Lawson, J. D. (1967), ‘Generalized Runge-Kutta processes for stable systems with large Lipschitz constants’, SIAM J. Numer. Anal. 4, 372–380.CrossRefGoogle Scholar
Martins, J. R. R. A., Sturdza, P. and Alonso, J. J. (2003), ‘The complex-step derivative approximation’, ACM Trans. Math. Software 29, 245–262.CrossRefGoogle Scholar
Mathias, R. (1996), ‘A chain rule for matrix functions and applications’, SIAM J. Matrix Anal. Appl. 17, 610–620.CrossRefGoogle Scholar
The MathWorks (2009 a), ‘numeric::expMatrix: The exponential of a matrix’. http://www.mathworks.com/access/helpdesk/help/toolbox/mupad/numeric/expMatr.html, retrieved on September 29, 2009.Google Scholar
The MathWorks (2009 b), ‘numeric::fMatrix: Functional calculus for numerical square matrices’. http://www.mathworks.com/access/helpdesk/help/toolbox/mupad/numeric/fMatrix.html, retrieved on September 29, 2009.Google Scholar
Moler, C. B. and Van Loan, C. F. (1978), ‘Nineteen dubious ways to compute the exponential of a matrix’, SIAM Rev. 20, 801–836.CrossRefGoogle Scholar
Moler, C. B. and Van Loan, C. F. (2003), ‘Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later’, SIAM Rev. 45, 3–49.CrossRefGoogle Scholar
Morai, L. and Pacheco, A. F. (2003), ‘Algebraic approach to the radioactive decay equations’, Amr. J. Phys. 71, 684–686.Google Scholar
Octave Version 3.2.2 (2009). http://www.octave.org.Google Scholar
Parlett, B. N. (1976), ‘A recurrence among the elements of functions of triangular matrices’, Linear Algebra Appl. 14, 117–121.CrossRefGoogle Scholar
Parlett, B. N. and Ng, K. C. (1985), Development of an accurate algorithm for exp(Bt). Technical Report PAM-294, Center for Pure and Applied Mathematics, University of California, Berkeley. Fortran program listings are given in an appendix with the same report number printed separately.Google Scholar
Paterson, M. S. and Stockmeyer, L. J. (1973), ‘On the number of nonscalar multiplications necessary to evaluate polynomials’, SIAM J. Comput. 2, 60–66.CrossRefGoogle Scholar
Peitgen, H.-O., Jürgens, H. and Saupe, D. (1992), Fractals for the Classroom, Part Two: Complex Systems and Mandelbrot Set, Springer, New York.Google Scholar
Phillips, G. M. (2000), Two Millennia of Mathematics: From Archimedes to Gauss, Springer, New York.CrossRefGoogle Scholar
Popolizio, M. and Simoncini, V. (2008), ‘Acceleration techniques for approximating the matrix exponential operator’, SIAM J. Matrix Anal. Appl. 30, 657–683.CrossRefGoogle Scholar
Psarrakos, P. J. (2002), ‘On the mth roots of a complex matrix’, Electron. J. Linear Algebra 9, 32–41.CrossRefGoogle Scholar
Pulay, P. (1966), ‘An iterative method for the determination of the square root of a positive definite matrix’, Z. Angew. Math. Mech. 46, 151.CrossRefGoogle Scholar
Rinehart, R. F. (1955), ‘The equivalence of definitions of a matric function’, Amer. Math. Monthly 62, 395–414.CrossRefGoogle Scholar
Roberts, J. D. (1980), ‘Linear model reduction and solution of the algebraic Riccati equation by use of the sign function’, Internat. J. Control 32, 677–687. First issued as report CUED/B-Control/TR13, Department of Engineering, University of Cambridge, 1971.CrossRefGoogle Scholar
Saad, Y. (1992), ‘Analysis of some Krylov subspace approximations to the matrix exponential operator’, SIAM J. Numer. Anal. 29, 209–228.CrossRefGoogle Scholar
Saad, Y. (2003), Iterative Methods for Sparse Linear Systems, second edn, SIAM, Philadelphia, PA, USA.CrossRefGoogle Scholar
Schroeder, M. (1991), Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise, W. H. Freeman, New York.Google Scholar
Serbin, S. M. and Blalock, S. A. (1980), ‘An algorithm for computing the matrix cosine’, SIAM J. Sci. Statist. Comput. 1, 198–204.CrossRefGoogle Scholar
Shampine, L. F. (2007), ‘Accurate numerical derivatives in MATLAB’, ACM Trans. Math. Software. #26, 17 pp.Google Scholar
Sidje, R. B. (1998), ‘Expokit: A software package for computing matrix exponentials’, ACM Trans. Math. Software 24, 130–156.CrossRefGoogle Scholar
Sidje, R. B., ‘Expokit’. http://www.maths.uq.edu.au/expokit, retrieved October 8, 2009.Google Scholar
Smith, M. I. (2003), ‘A Schur algorithm for computing matrix pth roots’, SIAM J. Matrix Anal. Appl. 24, 971–989.CrossRefGoogle Scholar
Squire, W. and Trapp, G. (1998), ‘Using complex variables to estimate derivatives of real functions’, SIAM Rev. 40, 110–112.CrossRefGoogle Scholar
Van Loan, C. F. (1975), A study of the matrix exponential. Numerical Analysis Report No. 10, University of Manchester, Manchester, UK. Reissued as MIMS EPrint 2006.397, Manchester Institute for Mathematical Sciences, The University of Manchester, UK, November 2006.Google Scholar
Van Loan, C. F. (1978), ‘Computing integrals involving the matrix exponential’, IEEE Trans. Automat. Control AC-23, 395–404.CrossRefGoogle Scholar
Van Loan, C. F. (1979), ‘A note on the evaluation of matrix polynomials’, IEEE Trans. Automat. Control AC-24, 320–321.CrossRefGoogle Scholar
Varga, R. S. (2000), Matrix Iterative Analysis, second edn, Springer, Berlin.CrossRefGoogle Scholar
Visser, C. (1937), ‘Note on linear operators’, Proc. Kon. Akad. Wet. Amsterdam 40, 270–272.Google Scholar
Ward, R. C. (1977), ‘Numerical computation of the matrix exponential with accuracy estimate’, SIAM J. Numer. Anal. 14, 600–610.CrossRefGoogle Scholar
Waugh, F. V. and Abel, M. E. (1967), ‘On fractional powers of a matrix’, J. Amer. Statist. Assoc. 62, 1018–1021.CrossRefGoogle Scholar
Yuan, D. and Kernan, W. (2007), ‘Explicit solutions for exit-only radioactive decay chains’, J. Appl. Phys. 101, 094907 1–12.CrossRefGoogle Scholar