# Two Taylor Algorithms for Computing the Action of the Matrix Exponential on a Vector
## 2 Algorithms for Computing the Action of the Matrix Exponential  
Let  
\[T_{m}(A)=\sum_{k=0}^{m}\frac{A^{k}}{k!}, \tag{1}\]  
be the Taylor approximation of order \(m\) devoted to the exponential of matrix \(A\in\mathbb{C}^{n\times n}\), and let \(v\in\mathbb{C}^{n}\) be a vector. In combination with the scaling and squaring method, the Taylor-based approach is concerned with computing \(e^{A}=\left(e^{2^{-s}A}\right)^{2^{s}}\approx\left(T_{m}(2^{-s}A)\right)^{2^ {s}}\)[6], where the nonnegative integers \(m\) and \(s\) are chosen to achieve full machine accuracy at a minimum computational cost. In our proposal, the values of \(m\) and \(s\) are calculated such that the absolute forward error for computing \(e^{s^{-1}A}v\) is less or equal to \(u=2^{-53}\), the so-called unit roundoff in IEEE double precision arithmetic. The absolute forward error of \(e^{s^{-1}A}v\) is bounded as follows:  
\[E_{af}(A,v)=\left\|\sum\limits_{k=m+1}^{\infty}\frac{A^{k}v}{s^{k}k!}\right\| \approx\left\|\frac{A^{m+1}v}{s^{m+1}(m+1)!}+\frac{A^{m+2}v}{s^{m+2}(m+2)!}\right\|. \tag{2}\]  
Hence, if we calculate \(s\) such that  
\[\left\|\frac{A^{m+1}v}{s^{m+1}(m+1)!}\right\|\leq u,\]  
i.e.,  
\[s=\left\lceil\sqrt[m+1]{\frac{\|A^{m+1}v\|}{(m+1)!u}}\right\rceil, \tag{3}\]  
and we verify that the following inequality is as well satisfied  
\[\left\|\frac{A^{m+1}v}{s^{m+1}(m+1)!}+\frac{A^{m+2}v}{s^{m+2}(m+2)!}\right\| \leq u, \tag{4}\]  
then, the absolute forward error of computing \(e^{s^{-1}A}v\) will be approximately less or equal to \(u\). Once \(m\) and \(s\) have been calculated, \(e^{A}v\) can be efficiently computed as follows:  
\[e^{A}v = \left(e^{A/s}\right)^{s}v=\overbrace{e^{A/s}e^{A/s}\cdots e^{A/s }e^{A/s}}^{s\text{ {times}}}v\] \[\cong \overbrace{\sum\limits_{k=0}^{m}\frac{A^{k}}{s^{k}k! }\sum \limits_{ \begin{subarray}{c}k=0\\ s-1\text{ times}\end{subarray} }^{ \begin{subarray}{c}A^{k}\\ s-1\text{ times}\end{subarray} }\cdots\sum\limits_{k=0}^{m}\frac{A^{k}}{s^{k}k! }\sum\limits_{k=0}^{m}\frac{A^{k}}{s^{k}k! }\,v}^{s}\] \[= \overbrace{\sum\limits_{k=0}^{m}\frac{A^{k}}{s^{k}k! }\sum \limits_{ \begin{subarray}{c}k=0\\ s-2\text{ times}\end{subarray} }^{ \begin{subarray}{c}A^{k}\\ s-1\text{ times}\end{subarray} }\cdots\sum\limits_{k=0}^{m}\frac{A^{k}}{s^{k}k! }\,w_{1}}^{s-2\text{ times}}\] \[= \overbrace{\sum\limits_{k=0}^{m}\frac{A^{k}}{s^{k}k! }\sum \limits_{ \begin{subarray}{c}k=0\\ s-2\text{ times}\end{subarray} }^{ \begin{subarray}{c}A^{k}\\ s^{k}k!\end{subarray} }\cdots\sum\limits_{k=0}^{m}\frac{A^{k}}{s^{k}k! }\,w_{2}}^ {s-1\text{ time}}\] \[= \overbrace{\sum\limits_{k=0}^{m}\frac{A^{k}}{s^{k}k! }}^{ \begin{subarray} {c}A^{k}\\ s^{k}k!\end{subarray} }w_{s-1}=w_{s},\]  
where \(w_{i}=\sum\limits_{k=0}^{m}\frac{A^{k}w_{i-1}}{s^{k}k! }\), \(i=1:s\), with \(w_{0}=v\). In this way, Algorithm 1 computes \(w=e^{A}v\), where \(A\in\mathbb{C}^{n\times n}\) and \(v\in\mathbb{C}^{n}\), starting with an initial value \(m\in\mathbb{N}\), without explicitly working out \(e^{A}\). First, in lines 1-4, vectors \(Av\), \(A^{2}v\), \(\cdots\), \(A^{m}v\), \(A^{m+1}v\), \(A^{m+2}v\) are computed and stored in the array of vectors \(V_{1}\), \(V_{2}\), \(\cdots\), \(V_{m+2}\), respectively. Then, lines 5-13 are used to determine the minimum value \(m\) and the corresponding value \(s\), calculated in line 7, taking into account expression (3), such that (4) is fulfilled. Next, in lines 15-17, \(m\) is set to the maximum value allowed if expression (3) could not be satisfied. Finally, in lines 18-29, \(w=e^{A}v\) is computed according to (5). ```
1:\(V_{1}=Av\)
2:for\(k=2:m+2\)do
3:\(V_{k}=AV_{k-1}\)
4:endfor
5:\(f=0\)
6:while\(f==0\) and \(m\leq M\)do
7:\(s=\left\lceil\sqrt[n+1]{\frac{\left\|V_{m+1}\right\|}{(m+1)!u}}\right\rceil\)
8:if\(\left\|\frac{V_{m+1}}{s^{m+1}(m+1)!}+\frac{V_{m+2}}{s^{m+2}(m+2)! }\right\|\leq u\)then
9:\(f=1\)
10:else
11:\(m=m+1\)
12:\(V_{m+2}=AV_{m+1}\)
13:endif
14:endwhile
15:if\(f==0\)then
16:\(m=M\)
17:endif
18:\(w=v\)
19:for\(k=1:m\)do
20:\(w=w+V_{k}/(s^{k}k!