ETD

• matrix exponential
• multiprecision arithmetic
• numerical analysis
• numerical linear algebra
• scaling and squaring

The goal of this essay is to describe the multiprecision algorithm proposed by Fasi and Higham [hf19] for computing the exponential of a matrix. A Julia implementation has been developed as part of the work for this thesis.
The matrix exponential has many applications in fields such as network analysis [estd], control theory [h_book, §2] and Markov modeling [norris]. Its fundamental role in the solution of differential equations makes it ubiquitous across scientific disciplines, where high precision computations are sometimes required. Accurately computing the matrix exponential, however, can be challenging because the problem is highly sensitive to both the spectral properties and the (non)normality of the matrix [mvl25].
The algorithm will only be described in Chapter 4; the previous chapters cover all of the necessary background, starting from floating point arithmetic. All the steps leading to its description are covered either directly or indirectly through numerous references to the existing literature. This makes the discussion longer, but it allows us to treat the matrix exponential function, its properties and the computational methods to approximate it with full generality.
A reader familiar enough with the topics of the first chapters may gloss over them, using the introduction to each chapter and this general introduction as a guide.
The classic topics of floating point arithmetic, numerical errors and conditioning are treated in Chapter 1, with the aim of offering a review of the foundations of numerical analysis and, most importantly, of presenting through numerous examples how multiprecision arithmetic works in Julia at the time of writing. In particular, this chapter illustrates how to perform some elementary linear algebra computations in arbitrary precision using Julia.
Chapter 2 is concerned with matrix functions. Their definitions and basic properties are presented, focusing on those that are more relevant to the algorithms considered in this thesis. Ample space is devoted to the conditioning of matrix functions, as the notion of Fréchet derivative is discussed together with several of its properties.
Unlike the particular case of the matrix exponential, which is treated separately in the third chapter, computational methods for general matrix functions are not considered in detail, with the exception of the evaluation of matrix polynomials. In particular, the Paterson-Stockmeyer scheme is thoroughly described, as it constitutes an essential component of the multiprecision algorithm.
Chapter 3 focuses on the matrix exponential, the general topic of this thesis. The chapter begins by reviewing some elementary properties and conditioning results specific to this function, and then proceeds to consider computational methods. In particular, scaling and squaring is described in detail, focusing on Higham's classic implementation, on its limitations and on some of the improvements that have been proposed since.
All of this allows for a review of more recent literature on the subject and, more importantly, introduces the mathematical tools that are commonly employed to construct scaling and squaring algorithms and to analyze their behaviour. For example, such algorithms typically select the values of their main parameters based on some form of error analysis. In particular, some of the improvements described in this chapter are incorporated into the multiprecision algorithm by Fasi and Higham.
As already mentioned, the multiprecision algorithm by Fasi and Higham is presented in Chapter 4. It performs scaling and squaring, employing either Taylor or diagonal Padé approximants.
Unlike Higham's original algorithm, which is tailored for double precision, this one selects its parameter values based on an upper bound on the forward error of the chosen approximant to the matrix exponential and on some heuristic strategies. Both aspects are analyzed in detail. In general, all the steps of the algorithm are thoroughly described, using numerous pseudocode listings. The chapter concludes with a cost analysis.
Chapter 6 presents the numerical experiments that have been conducted to assess the accuracy of the resulting algorithm. Two experimental strategies are analyzed and compared, to fully motivate the testing procedure adopted. The set of matrices used for the numerical experiments extends the one used in the original work [hf19].
The algorithm has been tested in all its possible configurations and at different working precisions; the resulting variants are compared based on the accuracy achieved on the test problems. The obtained results are presented and commented.
Finally, conclusions are drawn and some possible improvements to this work are proposed.

References:
[hf19]: M. Fasi, N.J. Higham. “An Arbitrary Precision Scaling and Squaring Algorithm for the Matrix Exponential”, In: SIAM J. Matrix Anal. & Appl. 40.4 (2019), pp. 1233-1256. DOI: 10.1137/18M1228876
[h_book]: N.J. Higham. “Functions of Matrices”. SIAM, 2008. DOI: 10.1137/1.9780898717778 [estd]: E. Estrada. “The Structure of Complex Networks: Theory and Applications”. Oxford University Press, Oct. 2011.
[norris]: J.R. Norris. “Markov Chains”. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1997.
[mvl_25]: C. Moler, C. Van Loan. “Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later”. In: SIAM Review 45.1 (2003), pp.3-49. DOI: 10.1137/S00361445024180