An Extended-Rational Arnoldi Method for Large Matrix Exponential Evaluations

Abstract

The numerical computation of a matrix function such as $\exp {(-tA)V}$, where A is an $n\times n$ large and sparse matrix, V is an $n \times p$ block with $p\ll n$, and $t>0$ arises in various applications including network analysis, the solution of time-dependent partial differential equations (PDE’s) and others. In this work, we propose the use of the global extended-rational Arnoldi method for computing approximations of such functions. The derived method projects the initial problem onto the global extended-rational Krylov subspace $\mathcal {RK}^{e}_m(A,V)=\text {span}\{\prod \limits \nolimits _{i=1}^m(A+s_iI_n)^{-1}V,\ldots ,(A+s_1I_n)^{-1}V,V$ $,AV, \ldots ,A^{m-1}V\}$ of a low dimension. An adaptive procedure of getting the shifts $\{s_1,\ldots ,s_m\}$ during the algorithmic process is given and analyzed. Applications to the solution of time-dependent PDE’s and to network analysis are presented. Numerical examples are presented to show the performance of the global extended-rational Arnoldi process.

1 Introduction

Let $A\in \mathbb {R}^{n\times n}$ be a large, and sparse matrix, and let $V\in \mathbb {R}^{n\times p}$ with $p\ll n$. We are interested in approximating numerically parameter-dependent matrix functions of the form

$$\begin{aligned} U(t):=\exp {(-tA)}V, \quad t>0, \end{aligned}$$

(1.1)

The need to evaluate matrix functions of the forms (1.1) arises in various applications; in the numerical solution of time integration of ordinary differential equations (ODEs) see, e.g., [7, 8, 11, 13] and in network analysis to study diffusion processes taking place on a network [7, 11]. Here the parameter t represents time. When the matrix A is a small to medium size, the matrix functions given by (1.1) can be determined by the spectral factorization of A (if exists) or using other techniques by computing $\exp (A)$; see, e.g, [18, 19], for discussions on several possible definitions of matrix functions. In many applications, the matrix A is so large that it is impractical to use one of these techniques in [18, 19]. In this case, several projection methods have been developed. These methods consist of the projection of the initial problem (1.1) on an increasing sequence of Krylov subspace, transforming the large-scale problem into a reduced problem that can be solved by direct methods and whose solution is an approximation of the solution of the initial problem. In the context of approximating the action of a matrix function f(A) on some vector $v\in \mathbb {R}^n$, several polynomial methods [15, 20, 30] based on the standard Arnoldi and Lanczos Krylov methods have been proposed.

Another technique for the evaluation of matrix functions is the standard rational Arnoldi method. This process was first proposed by Ruhe [29] in the context of computing the eigenvalues and has been used during the past few years for the approximation of matrix functions, see, e.g., [13, 13, 14, 16, 24, 28]. Druskin et al. [13], applied the standard rational Arnoldi method (poles equal $\{\sigma _1,\sigma _2,\ldots ,\sigma _m\})$, to compute $u(t)=\exp {(-tA)\varphi }$, $u(t),\varphi \in \mathbb {R}^n$, with adaptive pole choices. They generated an orthonormal basis $\mathbb {V}_m\in \mathbb {R}^{n\times m}$ of the following rational Krylov subspace

$$\begin{aligned} \mathrm{span}\{\varphi ,(A+\sigma _1I_n)^{-1}\varphi ,(A+\sigma _2I_n)^{-1}(A+\sigma _1I_n)^{-1}\varphi ,\ldots ,\prod _{j=1}^m(A+\sigma _jI_n)^{-1}\varphi \}, \end{aligned}$$

where $I_n\in \mathbb {R}^{n\times n}$ is the identity matrix. The rational Arnoldi approximation is

$$\begin{aligned} u(t)\approx \Vert \varphi \Vert _2\mathbb {V}_m\exp {(-tH_m})e_1,\quad \forall t>0, \end{aligned}$$

where $H_m=\mathbb {V}_m^TA\mathbb {V}_m\in \mathbb {R}^{m\times m}$, $e_1=[1,0,\ldots ,0]^T\in \mathbb {R}^m.$ For more details see, [13, Algorithm 2.4].

In many applications, we need to evaluate the matrix function with a number of vectors, i.e., $f(A)v^{(1)}$, ...,$f(A)v^{(p)}$ where all p vectors $v^{(i)}\in \mathbb {R}^n$ are available in advance and are linearly independent. Which is equivalent to evaluate f(A)V where $V=[v^{(1)},\ldots ,v^{(p)}]\in \mathbb {R}^{n\times p}$. The natural approach is to consider the vectors $v^{(i)}$ one by one (separately) and then approximate for each vector, the action of a matrix function f(A) on a vector $v^{(i)}$. The computed approximations by using one of the standard rational or the polynomial Krylov methods based on these approaches are quite expensive when the number of vectors p increases for large-scale matrix A. Global Krylov subspace methods can be used as an alternative way to approximate f(A)V at the same time. Global Krylov subspace techniques were first proposed in [22] for solving linear systems of equations with multiple right-hand sides. It is a block method based on a non-standard inner product (Frobenius inner product). Global rational and polynomial Krylov methods have been applied in different kinds of large matrix problems such that matrix equations [9], matrix functions [4], model reduction [1], image processing [5] and others. In this paper, we introduce the global extended-rational Arnoldi method with both finite nonnegative and infinite poles $s_1,\ldots ,s_m,\infty$ to approximate the matrix functions in (1.1). The global extended-rational Krylov subspace is defined as the subspace of $\mathbb {R}^{n\times p}$ spanned by the vectors ($n \times p$ matrices).

$$\begin{aligned} V,\ldots ,A^{m-1}V, \;\mathrm{and}\; (A+s_1I_n)^{-1}V,(A+s_1I_n)^{-1}(A+s_2 I_n)^{-1}V,\ldots ,\prod \limits _{i=1}^{m}(A+s_iI_n)^{-1}V, \end{aligned}$$

which is a matrix subspace of $\mathbb {R}^{n \times p}$ and is denoted by

$$\begin{aligned} \mathcal {RK}_m^{e}(A,V):=\text {span}\left\{ V,(A+s_1I_n)^{-1}V,\ldots ,A^{m-1}V,\prod \limits _{i=1}^m(A+s_iI_n)^{-1}V\right\} . \end{aligned}$$

(1.2)

where $\{s_1,\ldots ,s_m\}$ are some selected finite and nonnegative parameters all distinct from the eigenvalues of A. We notice here that the subspace $\mathcal {RK}_m^{e}(A,V)$ is a subspace of $\mathbb {R}^{n \times p}$ so the vectors are blocks of size $n\times p$. This subspace can be seen as a combination of the rational and the polynomial Krylov subspaces. We assume that all the vectors (blocks) in (1.2) are linearly independent. The present paper discusses global extended-rational Krylov subspaces, for which the highest positive and negative powers are about the same; cf. (1.2). The derivation can be extended to the situation when the highest positive and negative powers differ significantly. Different recursion formulas have to be derived for this case. In the interest of brevity, we do not discuss this situation in the present paper.

This paper is organized as follows. In Sect.2 , we give some preliminaries and then introduce the global extended-rational Arnoldi process with some properties. These properties are simpler than those of the rational methods [1, 13, 14]. Sect. 3 describes the application of this process to the approximation of the matrix exponential of the form (1.1). An adaptive strategy for the selection of the finite shifts $(s_i)$, that are used in the construction of the global extended-rational Krylov subspace is also presented. Our adaptive strategy is based on the residual, which is defined from the initial value problem for the ODE systems. Numerical experiments with applications to the resolution of time integration of ODE systems and to network analysis are presented in Sect. 4. Our method is compared to some available methods based on standard and global Krylov subspaces.

2 The Global Extended-Rational Arnoldi Method

2.1 Preliminaries and Notations

We begin by recalling some notations and definitions that will be used throughout this paper. The Kronecker product $\otimes$ satisfies the following properties

• 1 $(A\otimes B)(C\otimes D)=AC\otimes BD.$

• 2 $(A\otimes B)^T=A^T\otimes B^T$.

Definition 2.1

[10] Let the matrices $M=[M_1,M_2,\ldots ,M_s]\in \mathbb {R}^{n\times sp}$ and $N=[N_1,N_2,\ldots ,N_\ell ]\in \mathbb {R}^{n\times \ell p}$ be partitioned into block columns $M_i$ and $N_i$ of size $n\times p$, respectively. Then the $\diamond$-product of the matrices M and N is given by

$$\begin{aligned} M^{T}\diamond N=[\langle N_j,M_i\rangle _F]_{i=1,2,\ldots ,s}^{j=1,2,\ldots ,\ell }\in \mathbb {R}^{s\times \ell }, \end{aligned}$$

where $\langle \cdot ,\cdot \rangle _F$ is the Frobenius inner product and $\Vert \cdot \Vert _F$ denotes the Frobenius matrix norm. We refer to the $\diamond$-product as the “diamond product”.The following proposition gives some properties of the $\diamond$-product.

Proposition 2.2

[3, 10] Let $A,B,C\in \mathbb {R}^{n\times ps}$, $D\in \mathbb {R}^{n\times n}$, $L\in \mathbb {R}^{p\times p}$, and $\alpha \in \mathbb {R}$. Then,

• 1 $(A+B)^T\diamond C=A^T\diamond C+B^T\diamond C$.

• 2 $A^T\diamond (B+C)=A^T\diamond B+A^T\diamond C$.

• 3 $(\alpha A)^T\diamond C=\alpha (A^T\diamond C)$.

• 4 $(A^T\diamond B)^T=B^T\diamond A$.

• 5 $(DA)^T\diamond B=A^T\diamond (D^TB)$.

• 6 $A^T\diamond (B(L\otimes I_s))=(A^T\diamond B)L$.

Proposition 2.3

[23] Let $\mathcal {V}_{m}=[V_1,\ldots , V_m]\in \mathbb {R}^{n\times mp}$, where $V_1,\ldots ,V_m$ are F-orthonormal, and let $Z\in \mathbb {R}^{m\times p}$. Then

$$\begin{aligned} \Vert \mathcal {V}_m(Z\otimes I_p)\Vert _F=\Vert Z\Vert _F. \end{aligned}$$

2.2 Description of the Process

Now, we describe the global extended-rational Arnoldi process to generate an F-orthonormal basis $\{V_1,V_2,\ldots ,V_{2m+2}\}$ with $V_i\in \mathbb {R}^{n\times p}$ for the global extended-rational Krylov subspace $\mathcal {RK}_{m+1}^{e}(A,V)$, and we derive some algebraic relations related to this process. The block vector $V_i$’s are said to be F-orthonormal, if

$$\begin{aligned} \langle V_j,V_k \rangle _F := \mathrm{trace}(V_k^TV_j)= \left\{ \begin{array}{ll} 1 &{}\quad j=k,\\ 0 &{}\quad j\ne k.\end{array}\right. \end{aligned}$$

The first two blocks $V_1$ and $V_2$ are computed via the formulas

$$\begin{aligned} \begin{array}{ll} V_1&{}=\dfrac{V}{\alpha _{1,1}},\\ V_2&{}=\dfrac{\widetilde{V}_2}{\alpha _{2,2}}, \quad \widetilde{V}_2=(A+s_1 I_n)^{-1}V-\alpha _{1,2}V_1 , \end{array} \end{aligned}$$

(2.1)

where $\alpha _{1,1}=\Vert V\Vert _F$, $\alpha _{1,2}=\langle (A+s_1 I_n)^{-1}V,V_1\rangle _F$ and $\alpha _{2,2}=\Vert \widetilde{V}_2\Vert _F$. To compute the block vectors $V_{2j+1}$ and $V_{2j+2}$, for $j=1,\ldots ,m-1$, we use the following formulas

$$\begin{aligned} \begin{array}{ccl} h_{2j+1,2j-1}V_{2j+1}&{}=&{}AV_{2j-1}-\sum \limits _{i=1}^{2j}h_{i,2j-1}V_i=\widetilde{V}_{2j+1},\\ h_{2j+2,2j}V_{2j+2}&{}=&{}(A+s_j I_n)^{-1}V_{2j}-\sum \limits _{i=1}^{2j+1} h_{i,2j}V_i=\widetilde{V}_{2j+2}, \end{array} \end{aligned}$$

(2.2)

where the coefficients $h_{1,2j-1},\ldots ,h_{2j,2j-1}$ and $h_{1,2j},\ldots ,h_{2j+1,2j}$ are determined so that the vectors satisfy the F-orthogonality condition

$$\begin{aligned} V_{2j+1}\bot _F V_1,\ldots ,V_{2j},\quad \text {and}\quad V_{2j+2}\bot _F V_1,\ldots ,V_{2j+1}. \end{aligned}$$

Thus, the coefficients $h_{1,2j-1},\ldots ,h_{2j,2j-1}$ and $h_{1,2j},\ldots ,h_{2j+1,2j}$ are written as

$$\begin{aligned} h_{i,2j-1}=\langle AV_{2j-1},V_i\rangle _F, \quad \text {and} \quad h_{i,2j}=\langle (A+s_j I_n)^{-1}V_{2j},V_i\rangle _F. \end{aligned}$$

(2.3)

The coefficients $h_{2j+1,2j-1}$ and $h_{2j+2,2j}$ are such that $\Vert V_{2j+1}\Vert _F=1$ and $\Vert V_{2j+2}\Vert _F=1$; respectively. Hence,

$$\begin{aligned} h_{2j+1,2j-1}=\Vert \widetilde{V}_{2j+1}\Vert _F, \text { and } h_{2j+2,2j}=\Vert \widetilde{V}_{2j+2}\Vert _F. \end{aligned}$$

(2.4)

The global extended-rational Arnoldi algorithm is summarized in the following algorithm (Algorithm 1).

The set of shifts $\{s_1,\ldots ,s_m\}$ is chosen a priori or adaptively during the algorithm. We will explain the selection shift in sect. 3. If all $h_{2j+1,2j-1}$ and $h_{2j+2,2j}$ are numerically nonzero, then Algorithm 1 determines an F-orthonormal basis $V_1,\ldots ,V_{2m+2}$ $(V_j\in \mathbb {R}^{n\times p})$ of the global extended-rational Krylov subspace $\mathcal {RK}^{e}_{m+1}(A,V)$. Algorithm 1 constructs also an upper block Hessenberg matrix $\mathcal {\widetilde{H}}_{2m}=[h_{i,j}]\in \mathbb {R}^{2(m+1)\times 2m}$. We now introduce the $2m\times 2m$ matrix given by

$$\begin{aligned} \mathcal {T}_{2m}=\mathcal {V}_{2m}^T\diamond A\mathcal {V}_{2m}=[t_{i,j}], \end{aligned}$$

(2.5)

where $t_{i,j}=\langle AV_j,V_i\rangle _F,$ $i,j=1,\ldots ,2m$. $\mathcal {T}_{2m}$ is the restriction of the matrix A to the extended-rational Krylov subspace $\mathcal {RK}^{e}_m(A,V)$. The matrices

$$\begin{aligned} \mathcal {V}_{2m}=[V_1,V_2,\ldots ,V_{2m}],\quad \mathcal {V}_{2m+1}=[V_1,V_2,\ldots ,V_{2m+1}], \end{aligned}$$

are made up of orthonormal block vectors $V_j\in \mathbb {R}^{n\times s}$.

Proposition 2.4

Let the matrix $A\in \mathbb {R}^{n\times n}$, and let $V\in \mathbb {R}^{n\times p}$. The F-orthonormal basis $V_1,\ldots ,V_{2m+1}$ determined by the recursion formulas (2.2) satisfies, for $j=1,\ldots ,m$

$$\begin{aligned} AV_{2j-1}\text { and }AV_{2j}\in \text {span}\{V_1,\ldots ,V_{2j+1}\} \end{aligned}$$

(2.6)

We notice that in the formulas given by (2.6), $\mathcal {T}_{2m}$ is a block upper Hessenberg matrix with $2\times 2$ blocks, since $\langle AV_{2j-1},V_i\rangle _F=0$ and $\langle AV_{2j},V_i\rangle _F=0$, ( for $j=1,\ldots ,m$; $i\ge 2j+2$).

Proposition 2.5

Assume that m steps of Algorithm 1 have been run and let $\widetilde{\mathcal {T}}_{2m}=\mathcal {V}^T_{2m+1}\diamond A\mathcal {V}_{2m}$, then we have the following relations

$$\begin{aligned} \begin{array}{rcl} A\mathcal {V}_{2m}&{}=&{}\mathcal {V}_{2m+1}(\widetilde{\mathcal {T}}_{2m}\otimes I_p),\\ &{}=&{}\mathcal {V}_{2m}(\mathcal {T}_{2m}\otimes I_p)+V_{2m+1}\left( \begin{bmatrix}t_{2m+1,2m-1},&{}\,t_{2m+1,2m}\end{bmatrix}E^T_m\otimes I_p\right) , \end{array} \end{aligned}$$

(2.7)

where the matrix $E_m=[e_{2m-1},e_{2m}]\in \mathbb {R}^{2m\times 2}$ corresponds to the last two columns of the identity matrix $I_{2m}$.

Proof

According to (2.6), we obtain $A\mathcal {V}_{2m}\in \mathcal {RK}^{e}_m(A,V)$, then there exists a matrix $T\in \mathbb {R}^{(2m+1)\times 2m}$ such that

$$\begin{aligned} A\mathcal {V}_{2m}=\mathcal {V}_{2m+1}(T\otimes I_p). \end{aligned}$$

Using properties of the $\diamond$-product, we obtain

$$\begin{aligned} \mathcal {V}_{2m+1}^T\diamond A\mathcal {V}_{2m}&=\mathcal {V}_{2m+1}^T\diamond [\mathcal {V}_{2m+1}(T\otimes I_p)]\\&=(\mathcal {V}_{2m+1}^T\diamond \mathcal {V}_{2m+1})T=T. \end{aligned}$$

It follows that $\widetilde{T}_{2m}=T.$ Since $\widetilde{T}_{2m}$ is an upper block Hessenberg matrix with $2\times 2$ blocks then $\mathcal {V}_{2m+1}(\widetilde{T}_{2m}\otimes I_p)$ can be decomposed as follows

$$\begin{aligned} \mathcal {V}_{2m+1}(\widetilde{\mathcal {T}}_{2m}\otimes I_p)=\mathcal {V}_{2m}(\mathcal {T}_{2m}\otimes I_p)+V_{2m+1}\left( \begin{bmatrix}t_{2m+1,2m-1}\,,&\,t_{2m+1,2m}\end{bmatrix}E^T_m\otimes I_p\right) . \end{aligned}$$

Which completes the proof. $\square$

The following proposition gives the entries of $\mathcal {T}_{2m}$ and $\widetilde{\mathcal {T}}_{2m}$ in terms of the recursion coefficients, which allows us to compute the entries quite efficiently.

Proposition 2.6

Let $\widetilde{\mathcal {T}}_{2m}=[t_{:,1},\ldots ,t_{:,2m}]$ and $\widetilde{\mathcal {H}}_{2m}=[h_{:,1},\ldots ,h_{:,2m}]$ be the upper block Hessenberg matrices where $h_{:,j}$ and $t_{:,j}\in \mathbb {R}^{2m+1}$ are the j-th column of $\widetilde{\mathcal {H}}_{2m}$ and $\widetilde{\mathcal {T}}_{2m}$, respectively. Then the odd columns are such that

$$\begin{aligned} t_{:,2j-1}=h_{:,2j-1} \quad \text {for } j=1,\ldots ,m. \end{aligned}$$

(2.8)

The even columns satisfy the following relations

$$\begin{aligned} t_{:,2}&=\dfrac{(\alpha _{1,1}-s_1\alpha _{1,2})e_1-s_1\alpha _{2,2}e_2-\alpha _{1,2}h_{:,1}}{\alpha _{2,2}}, \end{aligned}$$

(2.9)

and for $j=1\ldots ,m-1$

$$\begin{aligned} t_{:,2j+2}&=\dfrac{1}{h_{2j+2,2j}}\left[ -s_jh_{2j+2,2j}e_{2j+2}+e_{2j}-\sum \limits _{i=1}^{2j+1}h_{i,2j}(t_{:,i}+s_j e_i)\right] , \end{aligned}$$

(2.10)

where $e_i$ corresponds to the i-th column vector of the canonical basis $\mathbb {R}^{2m+1}$ and $\alpha _{1,1}, \alpha _{1,2}$ and $\alpha _{2,2}$ are defined from (2.1).

Proof

We have $t_{:,2j-1}=\mathcal {V}^T_{2m+1}\diamond AV_{2j-1}$. Therefore, (2.8) follows from the expression of $h_{:,2j-1}$ in (2.3). Using (2.1), we obtain

$$\begin{aligned} \alpha _{1,2}V_1+\alpha _{2,2}V_2=\alpha _{1,1}(A+s_1 I_n)^{-1}V_1. \end{aligned}$$

Multiplying this last equality by $(A+s_1 I_n)$ from the left gives

$$\begin{aligned} \alpha _{1,2}(A+s_1 I_n)V_1+\alpha _{2,2}(A+s_1 I_n)V_2=\alpha _{1,1}V_1. \end{aligned}$$

Then, the vector $AV_2$ is written as follows

$$\begin{aligned} AV_2=\dfrac{1}{\alpha _{2,2}}[(\alpha _{1,1}-s_1\alpha _{1,2})V_1-s_1\alpha _{2,2}V_2-\alpha _{1,2}AV_1]. \end{aligned}$$

The relation (2.9) is obtained by multiplying $AV_2$ by $\mathcal {V}_{2m+1}^T$ with the $\diamond$-product from the left since $t_{:,2}=\mathcal {V}_{2m+1}^T\diamond AV_2$. The formula (2.10) is obtained from the expression of $AV_{2j+2}$ for $j=1,\ldots ,m-1$. Thus, multiplying the second equality in (2.2) by $(A+s_j I_n)$ from the left gives

$$\begin{aligned} h_{2j+2,2j}(A+s_j I_n)V_{2j+2}=V_{2j}-\sum \limits _{i=1}^{2j+1}h_{i,2j}(A+s_j I_n)V_i. \end{aligned}$$

Then,

$$\begin{aligned} AV_{2j+2}=\dfrac{1}{h_{2j+2,2j}}\left[ -h_{2j+2,2j}s_jV_{2j+2}+V_{2j}-\sum \limits _{i=1}^{2j+1}h_{i,2j}(Av_i+s_jV_i)\right] . \end{aligned}$$

The expression (2.10) is easily obtained by multiplying $AV_{2j+2}$ by $\mathcal {V}_{2m+1}^T$ with the $\diamond$-product from the left. This concludes the proof of the proposition. $\square$

We notice that if A is a symmetric matrix, then the restriction matrix $\mathcal {T}_{2m}$ in (2.5) reduces to a symmetric and pentadiagonal matrix with the following nontrivial entries,

$$\begin{aligned} t_{i,2j-1}&=h_{i,2j-1}, \quad \text {for } i\in \{2j-3,\ldots ,2j+1\},\\ t_{1,2}&=\begin{bmatrix} \alpha _{1,1}-(t_{1,1}+s_1)\alpha _{1,2}\end{bmatrix}/\alpha _{2,2},\\ t_{2,2}&=-s_1-t_{2,1}\alpha _{1,2}/\alpha _{2,2},\\ t_{3,2}&=-t_{3,1}\alpha _{1,2}/\alpha _{2,2}. \end{aligned}$$

And for $j=1,\ldots ,m-1$

$$\begin{aligned} t_{2j+1,2j+2}&=\left( -s_jh_{2j+1,2j}-\sum \limits _{i=2j-1}^{2j+1}t_{2j+1,i}h_{i,2j} \right) /h_{2j+2,2j},\\ t_{2j+2,2j+2}&=-s_j-t_{2j+2,2j+1}h_{2j+1,2j}/h_{2j+2,2j}, \mathrm{and} \\ t_{2j+3,2j+2}&=-t_{2j+3,2j+1}h_{2j+1,2j}/h_{2j+2,2j}. \end{aligned}$$

3 Application to the Approximation of $U(t):=\exp (-tA)V,$ $t>0$

In this section, we will show how to use the global extended-rational Arnoldi algorithm to approximate the parameter-dependent matrix functions given in (1.1). The global extended-rational Krylov subspace $\mathcal {RK}^{e}_m(A,V)$ defined in (1.2) can be written as

$$\begin{aligned} \mathcal {RK}^{e}_m(A,V)=\{X_{2m}\in \mathbb {R}^{n\times p}|X_{2m}=\mathcal {V}_{2m}(\mathcal {Y}_{2m}\otimes I_p)\text { where} \mathcal {Y}_{2m}\in \mathbb {R}^{2m}\}. \end{aligned}$$

(3.1)

Recall that $U(t)=\exp {(-tA)}V$ is the solution of the following evolutionary equation

$$\begin{aligned} {\left\{ \begin{array}{ll} \begin{array}{ll} U^{'}(t)=-AU(t),&{}\quad t>0\\ U(0)=V,&{}\quad U(\infty )=0. \end{array} \end{array}\right. } \end{aligned}$$

(3.2)

The approximation of U(t) by using m steps of the global extended rational Arnoldi method is written as

$$\begin{aligned} U_{2m}(t)=\mathcal {V}_{2m}(\mathcal {Y}_{2m}(t)\otimes I_p),\quad \mathcal {Y}_{2m}(t)\in \mathbb {R}^{2m}. \end{aligned}$$

$\mathcal {Y}_{2m}(t)$ is determined such that the residual $R_{2m}(t)=U^{'}_{2m}(t)+AU_{2m}(t)$ with respect to the evolutionary equation (3.2) is F-orthogonal to $\mathcal {RK}^e_m(A,V)$, i.e.,

$$\begin{aligned} \mathcal {V}_{2m}^T\diamond R_{2m}(t)=0,\quad \forall t>0. \end{aligned}$$

We have $U_{2m}^{'}(t)=\mathcal {V}_{2m}(\mathcal {Y}_{2m}^{'}(t)\otimes I_p)$. According to the second equation in (2.7), and using $\diamond$-product properties, we get

$$\begin{aligned} \mathcal {Y}^{'}_{2m}(t)+\mathcal {T}_{2m}\mathcal {Y}_{2m}(t)=0,\quad t>0, \end{aligned}$$

where $\{\mathcal {V}_{2m},\mathcal {T}_{2m}\}$ is a pair of matrices generated by m steps of GERA algorithm, (Algorithm 1). The approximation $\mathcal {Y}_{2m}(t)$ satisfies the initial condition $\mathcal {Y}_{2m}(0)=\Vert V\Vert _Fe_1$ by using the fact that

$$\begin{aligned} U_{2m}(0)=\mathcal {V}_{2m}(\mathcal {Y}_{2m}(0)\otimes I_p)=V=\mathcal {V}_{2m}(\Vert V\Vert _Fe_1\otimes I_p). \end{aligned}$$

$e_1=[1,0,\ldots ,0]^T\in \mathbb {R}^{2m}$. Therefore, the approximation $\mathcal {Y}_{2m}(t)$ corresponds to the solution of the reduced evolutionary problem

$$\begin{aligned} {\left\{ \begin{array}{ll} \begin{array}{ll} \mathcal {Y}_{2m}^{'}(t)=-\mathcal {T}_{2m}\mathcal {Y}_{2m}(t), &{}\quad t>0\\ \mathcal {Y}_{2m}(0)=\Vert V\Vert _Fe_1, &{}\quad \mathcal {Y}_{2m}(\infty )=0, \end{array} \end{array}\right. } \end{aligned}$$

(3.3)

which gives

$$\begin{aligned} \mathcal {Y}_{2m}(t)=\Vert V\Vert _F\exp {(-t\mathcal {T}_{2m})}e_1, \quad t>0. \end{aligned}$$

(3.4)

Then, the approximate solution of U(t) is written as

$$\begin{aligned} U_{2m}(t)=\Vert V\Vert _F\mathcal {V}_{2m}(\exp {(-t\mathcal {T}_{2m})}e_1\otimes I_p),\quad t>0. \end{aligned}$$

(3.5)

In the following result, we derive the expression for the residual norm of $R_{2m}(t)$ that avoids computing matrix products with the large matrix A.

Proposition 3.1

Let $Y_{2m}(t)$ be the solution of the reduced evolutionary problem (3.3) and let $U_{2m}(t)$ be the approximation of U(t) obtained after m steps of the GERA algorithm (Algorithm 1). Then, the residual $R_{2m}(t)$ is given by the quantity

$$\begin{aligned} \begin{array}{rl} \Vert R_{2m}(t)\Vert _F&=\Vert \tau _mE^T_mY_{2m}(t)\Vert _F. \end{array} \end{aligned}$$

(3.6)

where $\tau _m=\begin{bmatrix}t_{2m+1,2m-1}\,,&\,t_{2m+1,2m}\end{bmatrix}$ and $E_m$ are defined in (2.7).

Proof

We have

$$\begin{aligned} R_{2m}(t)&=U_{2m}^{'}(t)+AU_{2m}(t)\\&=\mathcal {V}_{2m}(Y^{'}_{2m}(t)\otimes I_p)+A\mathcal {V}_{2m}(Y_{2m}(t)\otimes I_p)\\&=\mathcal {V}_{2m}[(Y^{'}_{2m}(t)+\mathcal {T}_{2m}Y_{2m}(t)\otimes I_p)]+V_{2m+1}(\tau _mE^T_mY_{2m}(t)\otimes I_p) \end{aligned}$$

and because $Y_{2m}(t)$ is the solution of (3.3), it follows that

$$\begin{aligned}&=V_{2m+1}(\tau _mE^T_mY_{2m}(t)\otimes I_p). \end{aligned}$$

An application of Proposition 2.3 to the Frobenius norm of $R_{2m}(t)$, we obtain

$$\begin{aligned} \Vert R_{2m}(t)\Vert _F=\Vert V_{2m+1}(\tau _mE^T_mY_{2m}(t)\otimes I_p)\Vert _F=\Vert \tau _mE^T_mY_{2m}(t)\Vert _F. \end{aligned}$$

$\square$

In what follows, we assume that the symmetric part of the matrix A is semidefinite positive. This assumption allows the evolutionary problem (3.2) to be well-posed; see, [21], for more details.

Lemma 3.2

[21, Section I.2.3] Let $A\in \mathbb {R}^{n\times n}$ such that its symmetric part is semidefinite positive. Then, we have the following bound

$$\begin{aligned} \Vert \exp (-tA)\Vert _2\le e^{-tw},\quad t\ge 0, \end{aligned}$$

(3.7)

where $w=-\mu (-A)\ge 0$, with $\mu (B)=\lambda _{max}(\frac{1}{2}(B+B^T))$ is the logarithmic 2-norm of the matrix B.

Proposition 3.3

Let $U(t)=\exp {(-tA)}V$ be the solution of the equation (3.2) such that (3.7) holds, and let $U_{2m}(t)$ be the approximate solution of U(t) given by (3.5). Then, we have the following upper bound of the error

$$\begin{aligned} \Vert U(t)-U_{2m}(t)\Vert _2 \le \bigg [\dfrac{1}{w}(1-e^{-wt})\bigg ]\, \max \limits _{\lambda \in [0,t]}\Vert R_{2m}(\lambda )\Vert _F:=\xi _{2m}(t), \end{aligned}$$

(3.8)

where w is a constant introduced given below in (3.7).

Proof

Define the approximate error as $E_{2m}(t):=U(t)-U_{2m}(t)$, the derivative of $E_{2m}(t)$ is computed as

$$\begin{aligned} E_{2m}^{'}(t)&=U^{'}(t)-U_{2m}^{'}(t). \end{aligned}$$

U(t) is the solution of the equation (3.2), then $U^{'}(t)=-AU(t).$ In the other hand, we have

$$\begin{aligned} U_{2m}^{'}(t)&=\mathcal {V}_{2m}(\mathcal {Y}_{2m}^{'}(t)\otimes I_p)\\&=-\Vert V\Vert _F\mathcal {V}_{2m}(\mathcal {T}_{2m}\exp {(-t\mathcal {T}_{2m})}e_1\otimes I_p)\\&=-\Vert V\Vert _F\mathcal {V}_{2m}(\mathcal {T}_{2m}\otimes I_p)(\exp {(-t\mathcal {T}_{2m})}e_1\otimes I_p)\\ \end{aligned}$$

according to the second equation in (2.7), we get

$$\begin{aligned}&=-[A\mathcal {V}_{2m}-V_{2m+1}(\tau _mE^T_m\otimes I_p)](\mathcal {Y}_{2m}(t)\otimes I_p)\\&=-A\mathcal {V}_{2m}(\mathcal {Y}_{2m}(t)\otimes I_p)+V_{2m+1}(\tau _mE^T_m\otimes I_p)(\mathcal {Y}_{2m}(t)\otimes I_p)\\&=-AU_{2m}(t)+V_{2m+1}(\tau _mE^T_m\mathcal {Y}_{2m}(t)\otimes I_p)\\ U_{2m}^{'}(t)&=-AU_{2m}(t)+R_{2m}(t). \end{aligned}$$

Therefore,

$$\begin{aligned} E_{2m}^{'}(t)&=U^{'}(t)-U_{2m}^{'}(t)\\&=-AU(t)+AU_{2m}(t)-R_{2m}(t)\\&=-AE_{2m}(t)-R_{2m}(t). \end{aligned}$$

Moreover, we have $E_{2m}(0)=V-V=0.$ Then the approximate error $E_{2m}$ satisfies the following equation

$$\begin{aligned} {\left\{ \begin{array}{ll} \begin{array}{ll} E_{2m}^{'}(t)=-AE_{2m}(t)-R_{2m}(t), &{}\quad t>0\\ E_{2m}(0)=0.&{} \end{array} \end{array}\right. } \end{aligned}$$

(3.9)

This equation is a particular case of the general differential Sylvester equation (see., e.g., [2, 17] for more details). Then the error $E_{2m}(t)$ is written as

$$\begin{aligned} E_{2m}(t)=-\int ^t_0\exp {(-(t-\lambda )A)}R_{2m}(\lambda )d\lambda , \quad t\ge 0. \end{aligned}$$

This formula can be used to obtain error bounds in terms of the residual $R_{2m}(t)$ and the norm of the matrix exponential. Then,

$$\begin{aligned} \Vert E_{2m}(t)\Vert _2&= \bigg \Vert \int ^t_0\exp (-(t-\lambda )A)R_{2m}(\lambda )d\lambda \bigg \Vert _2\\&\le \int ^t_0\Vert \exp (-(t-\lambda )A)R_{2m}(\lambda )\Vert _2d\lambda \\&\le \int ^t_0\Vert \exp (-(t-\lambda )A)\Vert _2\Vert R_{2m}(\lambda )\Vert _2d\lambda \\&\le \max \limits _{\lambda \in [0,t]}\Vert R_{2m}(\lambda ) \Vert _2\int ^t_0\Vert \exp (-(t-\lambda )A)\Vert _2d\lambda . \end{aligned}$$

According to the equation (3.7), we obtain

$$\begin{aligned} \Vert E_{2m}(t)\Vert _2&\le \max \limits _{\lambda \in [0,t]}\Vert R_{2m}(\lambda )\Vert _F\int ^t_0 e^{-(t-\lambda )w}d\lambda \\&\le \bigg [\dfrac{1}{w}(1-e^{-wt})\bigg ]\, \max \limits _{\lambda \in [0,t]}\Vert R_{2m}(\lambda )\Vert _F. \end{aligned}$$

$\square$

When the constant $w=0$, or w is too close to zero, the statement (3.8) can be replaced by

$$\begin{aligned} \Vert U(t)-U_{2m}(t)\Vert _2 \le t\, \max \limits _{\lambda \in [0,t]}\Vert R_{2m}(\lambda )\Vert _F, \end{aligned}$$

since

$$\begin{aligned} \dfrac{1-e^{-tw}}{w}\approx t, \text { when } w\approx 0. \end{aligned}$$

The generated specialized orthonormal basis of (1.2) depends on some convenient shifts, and an effective dynamical way of getting them during the algorithmic process is proposed in this section. Van den Eshof et al. [32] applied the shift and invert Krylov method (SIKM) to find approximations of the matrix function $\exp {(-tA)v},$ for some $v\in \mathbb {R}^n$, and $t>0$ is a user fixed parameter. They consider the m-th shift and invert Krylov subspace defined as follows

$$\begin{aligned} \mathrm{span}\{(\gamma A+ I)^{-1}v,\ldots ,(\gamma A+ I)^{-m}v\}, \end{aligned}$$

the shift $\gamma$ in [32] is set to $\gamma =t/10$. In numerous applications, several values $\{t_1,t_2,\ldots ,t_M\}$ are needed in the evaluation of $\exp (-tA)v$. A possible drawback of the SIKM with a fixed chosen $\gamma =t_i/10$, for some $t_i$, is that this method may yield an accurate approximation only for some $\exp (-t_iA)v$. Then, the SIKM must restart for several $t_i$ to provide a higher approximation of all $\exp (-t_iA)v$. Our aim is to apply the global extended-rational Arnoldi method described in Sect. 2, to yield a higher approximation of all $U(t_i)=\exp (-t_iA)V$. The proposed method computes approximations in the union of Krylov subspaces determined by positive powers of A and negative powers of $A+s_iI$, $(i=1,\ldots ,m)$. Then, following the choice in [32], we take the shifts $s_i$ as $s_i=1/t_i$. When $m\ge M$ the shifts can be directly chosen as $s_i=t_i^{-1}.$ But when $m<M$, the values $t_i$ cannot be all taken in the shifts. The optimal shifts $\{s_1,\ldots ,s_m\}$ are chosen on the set of $\{1/t_1,\ldots ,1/t_M\}$ by using the max of the error bound $\xi _{2m}(t)$ in the right hand side of (3.8), i.e., the $(m+1)$-th shift can be chosen as follows

$$\begin{aligned} \left\{ \begin{array}{ll} \widetilde{t}_{m+1}= \mathop {{{\,\mathrm{arg\,max}\,}}}\limits _{t\in \{t_1,\ldots ,t_M\}}\bigg (\bigg [\dfrac{1}{w}(1-e^{-wt})\bigg ]\,\max \limits _{\lambda \in ]0,t]}\Vert R_{2m}(\lambda )\Vert _F\bigg ), &{} \quad \text { if } w\ne 0\\ \widetilde{t}_{m+1}=\mathop {{{\,\mathrm{arg\,max}\,}}}\limits _{t\in \{t_1,\ldots ,t_M\}}\left( t\,\max \limits _{\lambda \in ]0,t]}\Vert R_{2m}(\lambda )\Vert _F\right) , &{}\quad \text { if } w= 0\\ s_{m+1} =\widetilde{t}_{m+1}^{-1} &{} .\\ \end{array} \right. \end{aligned}$$

$\Vert R_{2m}(t)\Vert _F$ is given by (3.6), and the first shift $s_1$ is chosen as $s_1=1/t_1$. Note that, the computation of the error bound $\xi _{2m}(t)$ in (3.8) is available by carrying out m steps of the global extended rational process and only involve small dimensional terms.

Following the idea proposed by Van Den Eshof and Hochbruck in [32] for the exponential function, we consider the following error estimate to decide numerically how convergence is detected to approximate U(t) by using $(m+1)$ steps of the global extended-rational Arnoldi algorithm.

$$\begin{aligned} \epsilon _{2m}(t):= \dfrac{\Vert U(t)-U_{2m}(t)\Vert _F}{\Vert U_{2m}(t)\Vert _F}\approx \dfrac{\delta _{2m}(t)}{1-\delta _{2m}(t)}:=\gamma _{2m}(t),\quad \forall t>0. \end{aligned}$$

(3.10)

where $\delta _{2m}:=\Vert U_{2(m+1)}(t)-U_{2m}(t)\Vert _F/\Vert U_{2m}(t)\Vert _F.$ The estimate error has been applied in [25] in the context of the extended Arnoldi method. The quantity $\gamma _{2m}(t)$ can be considered as a stopping criterion to decide how convergence is detected. The computation of $\gamma _{2m}(t)$ requires the evaluation of one more step of the algorithm, but it is helpful to compute an estimate of the error at step $m,(dim=2m)$. Define the $\infty$-estimate error and $\infty$-relative error by

$$\begin{aligned} \epsilon _{2m}:=\max \limits _{t_1,\ldots ,t_M}\epsilon _{2m}(t),\quad \text {and}\quad \gamma _{2m}:=\max \limits _{t_1,\ldots ,t_M}\gamma _{2m}(t). \end{aligned}$$

(3.11)

Algorithm 2 describes the approximations of $U(t)=\exp {(-tA)}V$. It is an iterative algorithm that recycles information for $\{t_1,\ldots ,t_M\}$. In this algorithm, we start by $\Sigma _c=\emptyset$, and at each iteration m, we look for the values $t\in \Sigma$ such that $\gamma _{2(m-1)}(t)<tol$, where $\gamma _{2(m-1)}(t)$ is given by (3.10). We put the values t, which verify this stopping criterion in the set $\Sigma _c$. This means that the approximate solutions $U_{2(m-1)}(t)$ are converged for all values $t\in \Sigma _c$. We terminate the iterations when $\Sigma _c=\Sigma$, i.e., the approximate solutions determined by the adaptive global extended-rational Arnoldi method are converged for all $t\in \{t_1,\ldots ,t_M\}$.

4 Numerical Experiments

In this section, we illustrate the performance of the adaptive global extended-rational Arnoldi method (AGERA) when approximating $U(t)=\exp {(-tA)}V$ for multiple values of $t\in \{t_1,\ldots ,t_M\}$ using ($\exp$-AGERA) in Algorithm 2. All experiments were carried out with MATLAB R2015a on a computer with an Intel Core i-3 processor and 3.89 GBytes of RAM. The computations were done with about 15 significant decimal digits. The numerical section includes a comparison of two approaches to approximate matrix functions of the form (1.1) by using the proposed method (poles equal $\{\infty ,s_1,\ldots ,s_m\})$ with respect to the Arnoldi method (poles equal $\infty$), and the adaptive rational method (poles equal $\{\sigma _1,\ldots ,\sigma _m\}$). The first approach (Approach 1) is based on the approximation of $\{f(A)v^{(1)},f(A)v^{(2)},\ldots ,f(A)v^{(p)}\}$, where $V=[v^{(1)},v^{(2)},\ldots ,v^{(p)}].$ The second approach (Approach 2) is based on the non-standard inner product (Frobenius inner product) to approximate f(A)V. We also evaluate matrix functions (1.1) by using the block Arnoldi method [31], which uses (standard) block Krylov subspaces. The latter spaces are the union of a (standard) block Krylov subspace determined by positive powers of A. Notice that when $V\in \mathbb {R}^n$, (i.e., $p=1$), the proposed method in Algorithm 1 simplifies to the standard method applied to a given matrix A and a single vector. We refer to this method as the standard extended-rational Arnoldi method (SERA). ($\exp$-AGERA) in Algorithm 2 is denoted by ($\exp$-ASERA) when $V\in \mathbb {R}^n$ to evaluate matrix functions in (1.1). In both approaches, the adaptive rational methods provide shifts $\sigma _i$ by using Druskin’s adaptive pole technique in [13].

Denote the approximate solutions determined by applying the standard Arnoldi method and the standard adaptive rational Arnoldi method by the ($\exp$-SA) and the ($\exp$-SARA), respectively. Similarly, the approximate solutions obtained by the global Arnoldi method and the global adaptive rational Arnoldi method are referred to as the ($\exp$-GA) and the ($\exp$-GARA), respectively. The approximate solutions are determined by applying the block Arnoldi method, which is referred to as the ($\exp$-BA).

$\exp$-ASERA, $\exp$-AGERA, $\exp$-SARA, and $\exp$-GARA methods require the solution of systems of equations. This is done by computing the Choleski factorization when possible; otherwise we compute an LU factorization. In all experiments, the matrix A satisfies $x^TAx\ge 0,\, \forall x\in \mathbb {R}^n$ . The block size p of V is 5. The values of time step t are taken to be 100 values uniformly distributed in the interval $[10^{-2},1]$. The different tables in this section report the dimension (dim) of larger space as soon as $\gamma _{dim}<2\cdot 10^{-7}$, the required CPU-time (Time) in seconds, and the $\infty$-estimate error with $\exp$-ASERA, $\exp$-SA, $\exp$-SEA, $\exp$-SARA, $\exp$-AGERA, $\exp$-GA, $\exp$-GEA, and $\exp$-GARA methods. These methods are adapted to two approaches (Approach 1, and 2). In Approach 1, $\exp$-ASERA, $\exp$-SA, $\exp$-SEA, and $\exp$-SARA, are applied separately to the following sequence pairs $\{(A,v^{(1)}),\ldots ,(A,v^{(p)})\}$, $(m\ll n)$. Dimensions of this approach which are listed in different tables, are given by $Dim=\sum _{i=1}^pdim(i)$, where dim(i) is the dimension of larger Krylov space associated to the pair $(A,v^{(i)})$ as soon as $\gamma _{dim(i)}<2\cdot 10^{-7}.$ $\gamma _{dim(i)}$ is the estimate error of $\exp {(-tA)v^{(i)}}$ by the standard Krylov subspace methods of dim(i). $\exp$-AGERA, $\exp$-GA, $\exp$-GEA, $\exp$-GARA and $\exp$-BA are applied to the pair (A, V).

4.1 Application to the Solution of Time-dependent Partial Differential Equations

Example 1

The purpose of this example is to illustrate the quality of the $\infty$-estimate error $\gamma _{2m}$ to the $\infty$-relative error $\epsilon _{2m}$ given by (3.11) when applying $\exp$-AGERA method to approximate U(t). Consider the matrix $-A\in \mathbb {R}^{n\times n}$ obtained from the three point centered finite difference discretization (CFDD) of the Laplacian operator in one and two dimensions with homogeneous Dirichlet boundary conditions. In both dimensions, we consider uniform discretization with n representing the number of internal grid points of the spatial domain. In one dimension, the spatial domain is the interval [0, 1]. The starting block vector $V\in \mathbb {R}^{n\times 5}$ is the pointwise discretization in [0, 1] of the following functions $x\mapsto x(1-x)$, $x\mapsto \sin (\pi x)$, $x\mapsto x(1-x)\cos (\pi x)$, $x\mapsto \sin (2\pi x)\cos (\pi x)$ and $x\mapsto x(1-x)\sin (\pi x)$. In two dimensions, the spatial domain is the square $[0,1]\times [0,1]$ with $n=n_0^2$, where $n_0$ is the number of internal grid points in each direction. The starting block vector is the discretization in $[0,1]\times [0,1]$ of the following functions $(x,y)\mapsto xy(1-x)(1-y)$, $(x,y)\mapsto \sin (\pi x)\sin (\pi y)$, $(x,y)\mapsto xy(1-x)(1-y)\cos (\pi y)$, $(x,y)\mapsto \sin (2\pi x)\sin (\pi y)$ and $(x,y)\mapsto \sin (\pi x)\sin (2\pi y).$ The plots in Figs. 1 and 2 display the $\infty$-estimate error (red) and the $\infty$-relative error (blue) for the Laplacian operator in one and two dimensions ($n=\{900,2500,4900\}$) versus the number of iterations.

As shown in these figures, we observe that the $\infty$-estimate error $\gamma _{2m}$ coincides in all iterations with the $\infty$- relative error $\epsilon _{2m}$ given by (3.11).

In this example, we also compare the relative error $\Vert U(t)-U_{2m}(t)\Vert _2$ with his upper bound $\xi _{2m}(t)$ given by (3.8). We consider the same data sets as used above in this example and we take $t=0.01$. The plots in Figs. 3 and 4 display the absolute error (red) and his upper bound (blue) for the Laplacian operator in one and two dimensions; respectively, versus the number of iterations.

Fig. 1

Comparison of the $\infty$-estimate error and the $\infty$-relative error for the Laplacian operator in one dimension

Fig. 2

Comparison of the $\infty$-estimate error and the $\infty$-relative error for the Laplacian operator in two dimensions

Fig. 3

Comparison of the absolute error and his upper bound given by (3.8) for the Laplacian operator in one dimension and $t=1$

Fig. 4

Comparison of the absolute error and his upper bound given by (3.8) for the Laplacian operator in two dimensions and $t=1$

Example 2

In this example, we consider the approximation of the solution of the following partial differential equations on the unit square $[0,1]\times [0,1]$ with Dirichlet homogeneous boundary conditions using the compared methods

$$\begin{aligned} \begin{array}{rll} \dfrac{\partial U}{\partial t}-\mathcal {L}_i(U)&{}=0 &{} on\, (0,1)^2\times (0,1)\\ U(x,y,t)&{}=0 &{} on \, \partial (0,1)^2 \,\forall t\in [0,1]\\ U(x,y,0)&{}=V&{} \forall x,y\in [0,1]^2. \end{array} \end{aligned}$$

(4.1)

The number of discretization in each direction is $n_0$ and the dimension of matrices is $n=n^2_0$. In this experiment, the matrices $A_1$ and $A_2\in \mathbb {R}^{n\times n}:n\in \{2704,10404,40804\}$, are coming from CFDD of the operators $\mathcal {L}_1$ and $\mathcal {L}_2$; respectively, given by (4.2).

$$\begin{aligned} \begin{array}{rl} \mathcal {L}_{1}(U)&{}=-(D_1U_x)_x-(D_2U_y)_y+Pe\bigg (\dfrac{1}{2}(v_1U_x+v_2U_y)+\dfrac{1}{2}((v_1u)_x+(v_2u)_y)\bigg ),\\ \mathcal {L}_{2}(U)&{}=-\Delta U+Pe\bigg (\dfrac{1}{2}(v_1U_x+v_2U_y)+\dfrac{1}{2}((v_1u)_x+(v_2u)_y)\bigg ), \end{array} \end{aligned}$$

(4.2)

where

$$\begin{aligned} D_1(x,y)= \left\{ \begin{array}{ll} 10^3 &{}\quad (x,y)\in [0.25,0.75]^2,\\ 1 &{}\quad \text {otherwise}, \end{array}\right. \quad D_2(x,y)=\dfrac{1}{2}D_1(x,y), \end{aligned}$$

$$\begin{aligned} v_1(x,y)=x+y, \quad v_2(x,y)=x-y. \end{aligned}$$

The Péclet number Pe in $\mathcal {L}_1(U)$ and $\mathcal {L}_2(U)$ is chosen to be $Pe=(n_0-2)/4$. This choice of Péclet numbers guarantees the matrix A to semidefinite postive [26]. The starting block vector V is the pointwise discretization of following functons

$$\begin{aligned} \{(x,y)\mapsto \sin (k\pi x)\sin (k\pi y)\,,\, k=1,2,\ldots 5\}, \end{aligned}$$

on the internal grid points. The approximation errors and timings are listed in Tables 1 and 2. These tables report results correspond to the approximation of $\exp {(-tA_1)V}$ and $\exp {(-tA_2)V}$, respectively. Timings show methods given by the second approach based on the non-standard inner product to be faster than those given by the first approach based on the standard inner product. Moreover, the solutions determined by $\exp$-SA, $\exp$-GA and $\exp$-BA methods can be seen to be less accurate than those obtained by the $\exp$-SARA, $\exp$-GARA, $\exp$-ASERA and $\exp$-AGERA methods. In all approaches, the proposed methods $\exp$-ASERA and $\exp$-AGERA yield significantly fast results than polynomial and rational Krylov Arnoldi methods.

Table 1 Example 1: approximation of $\exp {(-tA)}V$ for multiple values of n associated to the operator $\mathcal {L}_1(U)$, $p=5$

Table 2 Example 1: approximation of $\exp {(-tA)}V$ for multiple values of n associated to the operator $\mathcal {L}_2(U)$, $p=5$

4.2 Application to Network Analysis

A network is represented by a graph $\mathcal {G}=\{\mathcal {V},\mathcal {E}\}$, which consists of a set of nodes or vertices $\mathcal {V}=\{v_i\}_{i=1}^n$ and a set of edges $\mathcal {E}=\{\widehat{e}_k=\{v_i,v_j\}:\,v_i,v_j\in \mathcal {V}\}_{k=1}^{N_e}$ that connect the vertices. n is the total number of nodes and $N_e$ corresponds to the total number of edges in the network. The adjacency matrix associated with $\mathcal {G}$ is the matrix

$$\begin{aligned} a_{i,j}=\left\{ \begin{array}{ll} 1 &{} \quad \text{ if } \text{ there } \text{ is } \text{ an } \text{ edge } \text{ from } \text{ vertex }~v_i \text{ to } \text{ vertex } v_j \text{(when }~\mathcal {G}~\text{ is } \text{ directed) }\\ &{}\quad \text{ or } \text{ between } \text{ the } \text{ vertices }~v_i~\text{ and }~ v_j~\text{(when }~ \mathcal {G}~\text{ is } \text{ undirected) },\\ 0 &{}\quad \text{ otherwise }. \end{array} \right. \end{aligned}$$

The adjacency matrix is symmetric if the graph $\mathcal {G}$ is undirected and nonsymmetric otherwise. The graph Laplacian matrix L of the graph $\mathcal {G}$ is defined as $L=D-A$, where $D=\mathrm{diag}(d_1,d_2,\ldots ,d_n)$ with $d_i$ is the out-degree of a node $v_i$, i.e., $d=A\mathbf{1}$, where $\mathbf{1} =[1,1,\ldots ,1]^T\in \mathbb {R}^n$. The graph Laplacian matrix L is used in the diffusion equation on the graph $\mathcal {G}.$ Note that the matrix L is a symmetric matrix when the graph is undirected. The diffusion equation on directed graphs is written as the following first-order initial value problem

$$\begin{aligned} \left\{ \begin{array}{lcl} \dfrac{d}{dt}X(t)^T&{}=&{}-X(t)^TL,\quad t>0,\\ X(0)&{}= &{} V, \end{array}\right. \end{aligned}$$

where $X(t)\in \mathbb {R}^{n\times p}$ is a block vector of concentrations at time t of a substance that is diffusing on the graph [6]. The solution of this equation is given explicitly by

$$\begin{aligned} X(t)=\exp {(-tL^T)}V. \end{aligned}$$

(4.3)

In examples 3 and 4, we consider some real-world networks which can be found in the SuiteSparse Matrix Collection [12]. The block vector V is chosen as

$$\begin{aligned} V=\begin{bmatrix} 1 &{}\quad 1 &{}\quad 1 &{}\quad 1 &{}\quad 0\\ 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1\\ 1 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0\\ 1 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0\\ \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots \\ 1 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0\\ 1 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0\\ 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \end{bmatrix}\in \mathbb {R}^{n\times 5}. \end{aligned}$$

Example 3

In this example, we present the quality of the $\infty$-estimate error $\gamma _{2m}$ with respect to the $\infty$-relative error $\epsilon _{2m}$ given by (3.11) when applying the $\exp$-AGERA method to approximate X(t) in (4.3). The plots in Figs. 5 and 6 display the $\infty$-estimate error (red) and the $\infty$-relative error (blue) for some undirected graphs (email $n=1133$, minnesota $n=2642$) and directed graphs (Air500 $n=500$, Roget $n=1022$) respectively, versus the number of iterations.

Fig. 5

Comparison of the $\infty$-estimate error and the $\infty$-relative error for undirected graphs

Fig. 6

Comparison of the $\infty$-estimate error and the $\infty$-relative error for directed graphs

Figures 5 and 6 are analogous to Figs. 1 and 2 and show that the $\infty$-estimate error $\gamma _{2m}$ gives higher precision for the behavior of the $\infty$- relative error $\epsilon _{2m}$ given by (3.11).

The relative error $\Vert U(t)-U_{2m}(t)\Vert _2$ is also compared with his upper bound $\xi _{2m}(t)$ in this example for $t=1$. Figures 7 and 8 show the computed results.

Fig. 7

Comparison of the absolute error and his upper bound given by (3.8) for undirected graphs, $t=1$.

Fig. 8

Comparison of the absolute error and his upper bound given by (3.8) for directed graphs, $t=1$.

Example 4

In this example, we compare the $\exp$-ASERA and the $\exp$-AGERA to the polynomial and rational methods to approximate X(t) given by (4.3) for some undirected and directed graphs. Tables 3 and 4 display computed results and show that approximations computed from the second approach return fast results than the first approach. Moreover, the $\exp$-AGERA method requires fewer iterations and CPU-time than $\exp$-GA, $\exp$-BA and $\exp$-GARA methods.

Table 3 Example 4: approximation of $X(t)=\exp {(-tL)}V$ for undirected graphs, $p=5$

Table 4 Example 4: approximation of $X(t)=\exp {(-tL^T)}V$ for directed graphs, $p=5$

Example 5

In the previous examples, the shifted inverses are computed via an LU decomposition. In this last experiment, we usde the block Arnoldi method (BFOM) and the block GMRES method (BGMRES) [31] to solve the shifted linear equations involved in our proposed method. For both methods, the stopping criteria was determined when the residual is below $10^{-10}.$ We considered the following matrices, $\mathcal {L}_1$ $(n=40804)$, $\mathcal {L}_2$ $(n=40804)$, as-22july06 ($n=22963$) and enron $(n=36692)$ used in the previous examples. The obtained approximate errors and CPU times are listed in Table 5 when the $\exp$-AGERA(LU), $\exp$-AGERA(BFOM) and $\exp$-AGERA(BGMRES) methods are applied to evaluate $\exp (-tA)V$. As this table shows, the three methods produce the same approximation errors at approximately the same time. We notice that block Krylov subspace methods with preconditionners could be more interesting than using LU decomposition when the involved matrices are not structured.

Table 5 Example 5: approximation of $X(t)=\exp {(-tA)}V$, $p=5$

5 Conclusion

This paper describes the global extended-rational Arnoldi method for large matrix exponential evaluations of the form $\exp {(-tA)V}$ for multiple values of time t, that appear in the solution of time-dependent PDE’s and in network analysis. The generated specialized orthonormal basis of (1.2) depends on some convenient shifts, and an adaptive strategy for the selection of the finite shifts $(s_i)$ is also analyzed. Illustrative numerical experiments are presented for solving some well-known time-integration ODE’s. Also, applications to network analysis are given. The computed examples illustrate the effectiveness of the proposed methods.