# Two Taylor Algorithms for Computing the Action of the Matrix Exponential on a Vector
## 2 Algorithms for Computing the Action of the Matrix Exponential
)\)
21:endfor
22:\(A=A/s\)
23:for\(i=2:s\)do
24:\(v=w\)
25:for\(k=1:m\)do
26:\(v=Av\)
27:\(w=w+v/k!\)
28:endfor
29:endfor
```  
**Algorithm 1** Given a matrix \(A\in\mathbb{C}^{n\times n}\), a vector \(v\in\mathbb{C}^{n}\), and minimum \(m\) and maximum \(M\) Taylor polynomial orders, \(m,M\in\mathbb{N}\), this algorithm computes \(w=e^{A}v\in\mathbb{C}^{n}\) by (5). On the contrary, if an absolute backward error analysis for computing \(e^{s-1}Av\) were considered, see (10), (11), (13)-(15), and (22) from [25], then  
\[E_{ab}(A,v) = \left\|\sum_{k\geq 0}\frac{\left(-1\right)^{k}A^{m+1+k}v}{s^{m+1+k }k!m!(m+1+k)}\right\|\] \[\approx \left\|\frac{A^{m+1}v}{s^{m+1}(m+1)!}-\frac{A^{m+2}v}{s^{m+2}m!( m+2)}\right\|.\]  
As in both cases in which the first term of these absolute errors coincides, Algorithm 1 could be easily modified for computing \(e^{s-1}Av\) such that \(E_{ab}\leq u\). To do this, only the condition expression in line 8, which checks whether convergence is reached, should be replaced by \(\left\|\frac{V_{m+1}}{s^{m+1}(m+1)!}-\frac{V^{m+1}}{s^{m+2}(m+2)! }\right\|\leq u\). An alternative formulation to expression (2) in the absolute backward error estimation would have been to consider only the first of the terms. In this way, starting from a minimum value of \(m\), the value of \(s\) is computed from the expression (3), which will already ensure that the error committed will be less or equal to \(u\). With that assumption, together with the objective of reducing the matrix-vector products of the previous algorithm, we designed Algorithm 2, which determines the appropriate values of \(m\) and \(s\) that satisfy both purposes. ```
1:\(V_{1}=Av\)
2:for\(k=2:m+1\)do
3:\(V_{k}=AV_{k-1}\)
4:endfor
5:\(s=\left\lceil\frac{\|V_{m+1}\|}{(m+1)!u}\right\rceil\)
6:\(p=ms\)
7:\(f=0\)
8:while\(f=0\) and \(m<M\)do
9:\(m=m+1\)
10:\(V_{m+1}=AV_{m}\)
11:\(s_{1}=\left\lceil\frac{m+1}{(m+1)!u}\right\rceil\)
12:\(p_{1}=ms_{1}\)
13:if\(p_{1}\leq p\)then
14:\(p=p_{1}\)
15:\(s=s_{1}\)
16:else
17:\(m=m-1\)
18:\(f=1\)
19:endif
20:endwhile
21:\(w=v\)
22:for\(k=1:m\)do
23:\(w=w+V_{k}/(s^{k}k! )\)
24:endfor
25:\(A=A/s\)
26:for\(i=2:s\)do
27:\(v=w\)
28:for\(k=1:m\)do
29:\(v=Av\)
30:\(w=w+v/k!\)
31:endfor
32:endfor
```  
**Algorithm 2** Given a matrix \(A\in\mathbb{C}^{n\times n}\), a vector \(v\in\mathbb{C}^{n}\), and minimum \(m\) and maximum \(M\) Taylor polynomial orders, \(m,M\in\mathbb{N}\), this algorithm computes \(w=e^{A}v\in\mathbb{C}^{n}\) by (5). For \(t\), in lines 5-20, the number of matrix-vector products \(p\) required, obtained as \(m\times s\), employing two consecutive values of \(m\) and their corresponding values of \(s\), is compared in each iteration of the while loop. The procedure concludes when the number of products associated with a given degree \(m\) of the Taylor polynomial is greater than that obtained with the immediately preceding degree. Table 1 shows the computational and storage costs of Algorithms 1 and 2. The computational cost depends on the parameters \(m\) and \(s\) and it is specified in terms of the required number of matrix-vector products. The storage costs is expressed as the number of matrices and vectors with which the algorithms work. \begin{table}
\begin{tabular}{l l l l} \hline \hline  & **Computational Cost** & **Matrices to Be Stored** & **Vectors to Be Stored** \\ \hline Algorithm 1 & \(ms+2\) & 1 & \(m+4\) \\ \hline Algorithm 2 (\(m<M\)) & \(ms+2\) & 1 & \(m+4\) \\ Algorithm 2 (\(m=M\)) & \(ms+1\) & 1 & \(m+3\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Computational and storage costs for Algorithms 1 and 2.