Differential Equations and the Matrix Exponential

Problem Description

A linear differential equation y' = Ay with initial condition y(0) = y_0 has the solution y(t) = exp(At)y_0, where the matrix exponential

exp(At) = I + At + (At)^2/2! + (At)^3/3! + ...

The solutions to nonlinear differential equations can be written in integral forms involving the exponential of the matrix defining the linear part of the equation and these are the basis of various numerical methods, in particular the class of exponential integrators. Two problems arise:

Compute the exponential of the n-by-n matrix A.
Compute the action of the exponential of the n-by-n matrix A on a vector b or matrix B: exp(A)*b or exp(A)*B.

The second problem is particularly important when A is large and sparse and it is impractical to form exp(A) explicitly.

Research

We have made significant improvements to the scaling and squaring method for computing exp(A), which is the most widely used method. The scaling and squaring algorithm used by the MATLAB expm function was developed in Manchester, and that algorithm has recently been improved so as to avoid the problem of overscaling.

We have also made significant progress in computing the Fréchet derivative, and estimating the condition number, of the matrix exponential. In particular, we have shown how to efficiently intertwine computation of exp(A) with estimation of its condition number.

Most recently, we have developed an algorithm for the exp(A)*B problem that combines the scaling part of the scaling and squaring method with a truncated Taylor series approximation to the exponential. In our experiments this algorithm has proved superior to Krylov-based methods and ODE integrators such as the MATLAB functions ode45 and ode15s.

Publications (recent)

Awad Al-Mohy, and Nicholas J. Higham, Computing the Action of the Matrix Exponential, with an Application to Exponential Integrators, SIAM J. Sci. Comp. 33 (2): 488-511, 2011. MATLAB codes.
Nicholas J. Higham, and Awad Al-Mohy, Computing Matrix Functions, Acta Numerica 19: 159-208, 2010.
Awad Al-Mohy, and Nicholas J. Higham, The Complex Step Approximation to the Fréchet Derivative of a Matrix Function, Numer. Alg. 53(1): 133-148, 2010. Published version.
Awad Al-Mohy, and Nicholas J. Higham, A New Scaling and Squaring Algorithm for the Matrix Exponential, SIAM J. Matrix Anal. Appl. 31(3): 970-989, 2009. MATLAB codes.
Nicholas J. Higham, Functions of Matrices: Theory and Computation, SIAM, 2008. xx+425 pages, ISBN 978-0-898716-46-7.

Events

MIMS New Directions Workshop on Functions of Matrices, University of Manchester, May 15-16, 2008.

People

Our team at Manchester involves:

NEWS