### Mathematical Software for Computing Matrix Functions

**Submitting Institution**

University of Manchester**Unit of Assessment**

Mathematical Sciences**Summary Impact Type**

Technological**Research Subject Area(s)**

Mathematical Sciences: Pure Mathematics, Statistics

Information and Computing Sciences: Computation Theory and Mathematics

**Download original**

PDF**Summary of the impact**

Functions of matrices underpin many of the fundamental algorithms used in the finance, engineering and pharmaceutical industries. Our research has provided the state of the art algorithms for computing the most common matrix functions. The algorithms have been implemented commercially in MATLAB (with almost 2 million users) and the Numerical Algorithms Group (NAG) Ltd Library; as well as in open source packages such as R and Eigen. Software companies have enjoyed direct impact through improved products and increased revenues, whilst the greater indirect impact is for the users of the software, leading to acceleration in the pace of science and engineering worldwide.

**Underpinning research**

The impact is based on research that took place in the unit of assessment from 1993-date, with the first major publication in 2000. The key researchers were

Professor Nick Higham (1993-date).

Professor Françoise Tisseur (1997-date: PDRA '98-`00, Lecturer `01-'05, SL
'06-'07, Reader '09-'11, Professor '12-date).

Dr Philip Davies (PhD student '98-'00, PDRA '01-'04).

The algorithms on which this case study is based are:

- Scaling and squaring algorithm for the matrix exponential [1]. This algorithm improves on earlier scaling and squaring algorithms by choosing the amount of scaling and the Padé degree dynamically based on the matrix norm and precomputed constants determined from backward error analysis.
- Inverse scaling and squaring algorithm for the matrix logarithm [4, Sec. 11.5]. This algorithm uses a dynamic choice of number of square roots and Padé degree.
- The Schur-Parlett algorithm for computing arbitrary matrix functions [2].
- An algorithm for matrix 1-norm estimation [3] that generalizes to block form and provides more accurate estimates than an earlier algorithm of Higham that is the basis of the LAPACK condition number estimator.

**References to the research**

The research has been published in leading, high impact numerical analysis journals and has been widely cited. Citations are shown for the Web of Science (WOS) and Google Scholar (GS) as of 9-8-13.

[1] N. J. Higham, The scaling and squaring method for the matrix
exponential revisited, SIAM J. Matrix Anal. Appl., 26(4):1179-1193, 2005.
DOI . [WoS: 98, GS: 201].

doi.org/10.1137/04061101X

[2] P. I. Davies and N. J. Higham, A Schur-Parlett algorithm for
computing matrix functions, SIAM J. Matrix Anal. Appl., 25(2):464-485,
2003. DOI . [WoS: 44, GS: 96].

doi.org/10.1137/S0895479802410815

[3] N. J. Higham and F. Tisseur. A block algorithm for matrix 1-norm estimation, with an application to 1-norm pseudospectra. SIAM J. Matrix Anal. Appl., 21(4):1185-1201, 2000. DOI . [WoS: 29, GS: 83]. doi.org/10.1137/S0895479899356080

The following research monograph includes treatments of [1-3] and contains a new algorithm for the matrix logarithm.

[4] N. J. Higham, Functions of Matrices: Theory and Computation, SIAM,
2008. xx+425 pages, . [WoS: 195, GS: 494]

http://books.google.co.uk/books?hl=en&lr=&id=S6gpNn1JmbgC&oi=fnd&pg=PR3&dq=N.+J.+Higha
m,+Functions+of+Matrices:+Theory+and+Computation,+SIAM,+2008

**Details of the impact**

**Context**

Matrix functions underpin computer simulations used to inform decision
making across almost all industrial sectors. The need for high-quality
simulation results makes it increasingly important to enable the accurate
and efficient computation of matrix functions. Our research has provided
the first reliable and efficient algorithm for computing general matrix
functions, as well as the state of the art algorithms for the matrix
exponential and matrix logarithm, which play a key role in control theory.
MATLAB, from The MathWorks (head office in Natick, MA, USA, with other
offices including in Cambridge, UK) is a commercial mathematical software
system with almost 2 million users in industry and academia. Its
associated toolboxes and Simulink, an environment for multidomain
simulation, run within MATLAB and provide specialist capabilities that are
widely used in the engineering and finance sectors. The Numerical
Algorithms Group (NAG) Ltd Library is a product of NAG Ltd. (head office
in Oxford UK), which has as its core business the production and sale of
mathematical and statistical software components, including libraries.

**Pathways to Impact**

Higham and Tisseur have long-standing professional relationships with
colleagues from NAG and The MathWorks, going back to the 1980s. As a
result of these links, the research reported here has been strongly
influenced by the needs of NAG and The MathWorks; and both companies have
been in a position to rapidly incorporate the resulting algorithms into
their products. A Knowledge Transfer Partnership (2010-2013) funded a
full-time KTP Associate to translate algorithms for matrix functions
developed by Higham and Tisseur into NAG products.

**Reach and Significance of the Impact**

The research has reached a large proportion of the relevant community
through its incorporation in widely used commercial and open source
software, including R [S4], Eigen [S5] and Scipy (Python) [S6]. Indeed,
the majority of end users of matrix functions will be using the algorithms
that are the focus of this case study, albeit unknowingly. We have found
the non-academic impact of open source implementations of our algorithms
impossible to quantify, and so instead quantify the impacts of
implementations made by the commercial companies The Mathworks and NAG.

**The MathWorks**

The Mathworks state that [S2] "*it is difficult to measure direct
economic impact of the ... algorithms, it is inarguable that your
contribution to Matlab and MathWorks' product line has been significant
in accelerating the pace of engineering and science in a wide variety of
industries from aerospace and automotive to financial and
pharmaceutical.*" Nonetheless all copies of MATLAB licensed within
the assessment period contained our algorithms and the annual revenue of
The Mathworks in 2012 was US$750 million [S7], mostly due to licensing
income.

Specific direct impacts for the company are detailed below:

- The MathWorks incorporated the new algorithm [2] in MATLAB 7.0. From 2004 to 2011 this was the only numerically reliable code for general matrix functions available in any commercial software, giving The MathWorks a commercial advantage and its customers a unique capability.
- A crucial aspect of MATLAB functionality is its ability to detect ill conditioned problems and warn the user of ill conditioning. From MATLAB 6.0 (2000) the condition number of a matrix is estimated using the block algorithm of [3], which provides more reliable estimates than the previous point algorithm. This block algorithm has continuing impact as a key component of MATLAB, used in the ordinary differential equation solvers and fitting functions used in the Statistics and Curve Fitting Toolboxes [S2].
- Our algorithms for the principal matrix logarithm [4, Alg. 11.11] and
matrix exponential [1] are "
*an intrinsic part of MathWorks' Control Systems Toolbox, underpinning the reliability of MATLAB in control engineering applications*" [S2]. - The implementation of our matrix exponential algorithm in MATLAB function expm led to a faster, more accurate code and better maintainability of the code base due to the use of an M-file rather than C [S1].

**NAG**

Specific direct impacts for NAG within the assessment period are detailed below:

- A new code f01ecf (f01ecc) introduced in Mark 22 (2011) of the NAG Library for computing the matrix exponential using the algorithm of [1].
- A new family of NAG Library codes for evaluating general matrix functions by the algorithm of [2] and the matrix logarithm using the algorithm of [4, Alg. 11.11] was released in Mark 23 (spring 2012).
- A NAG Library code f0y4d for matrix norm estimation using the block algorithm of [4] was released at Mark 24 (spring 2013).

The new matrix function codes are helping NAG gain more revenue across all sectors, both from new customers and from existing users who are more likely to renew with the new features. The total additional income resulting from these codes, from new licenses plus renewals, is estimated by NAG as £100k during the project (January 2010 - July 2013), £240k in the year after project completion, with a further doubling for each of the following two years, which is very significant for a company with about 70 FTE staff [S3].

**Sources to corroborate the impact **

[S1] Email from Principal Numerical Analyst at The MathWorks, August 19,
2005.

(Supports claim of increased speed and accuracy and better maintainabiilty
of the MATLAB function expm)

[S2] Letter from Manager, The MathWorks, May 21, 2013.

(Supports the claims of increasing functionality and accuracy in MATLAB)

[S3] Letter from VP for Sales and Marketing, NAG, July 22, 2013.

(Supports financial claims and the importance of the algorithms for NAG)

[S4] Vincent Goulet, Christophe Dutang, Martin Maechler, David Firth, Marina Shapira, Michael Stadelmann, R package expm: Matrix exponential, Computation of the matrix exponential and related quantities. expm-developers@lists.R-forge.R-project.org, July 2010 onwards. http://cran.r-project.org/web/packages/expm/index.html (Demonstrates that algorithm is implemented in R)

[S5] J. Niesen, Matrix functions module for Eigen C++ template library for linear algebra. http://eigen.tuxfamily.org/dox (Demonstrates that algorithm is implemented in Eigen)

[S6] Comments at http://nickhigham.wordpress.com/2013/03/10/siam-conference-on-computational-science-and-engineering-2013. (Demonstrates that algorithm is implemented in Python)

[S7] Matlab factsheet (Confirms the revenue of The Mathworks in 2012)