An extended nonsymmetric block Lanczos method for model reduction in large scale dynamical systems

Abstract

In this paper, we propose an extended block Krylov process to construct two biorthogonal bases for the extended Krylov subspaces $\mathbb {K}_{m}^e(A,V)$ and $\mathbb {K}_{m}^e(A^{T},W)$, where $A \in \mathbb {R}^{n \times n}$ and $V,~W \in \mathbb {R}^{n \times p}$. After deriving some new theoretical results and algebraic properties, we apply the proposed algorithm with moment matching techniques for model reduction in large scale dynamical systems. Numerical experiments for large and sparse problems are given to show the efficiency of the proposed method.

1 Introduction

This paper presents a new projection method for reducing the order of large scale dynamical Multiple-Input Multiple-Output (MIMO) linear time invariant (LTI) systems expressed in state-space form as

$$\begin{aligned} \left\{ \begin{array}{lll} \dot{x}(t) = A\,x(t) +B\,u(t); \;\;\; x(t_0)=x_0\\ y(t) = C\,x(t)\\ \end{array} \right. \end{aligned}$$

(1)

where $x(t)\in \mathbb {R}^{n}$ is the state vector, $u(t),~y(t)\in \mathbb {R}^{p}$ are the input and the output vectors of the system (1), respectively. The matrix $A \in \mathbb {R}^{n \times n}$ is assumed to be large, sparse and nonsingular, and $B,~C^{T} \in \mathbb {R}^{n \times p}$.

This method consists of projecting the original problem (1) onto an extended block Krylov subspace to obtain a low order model. We recall that an extended Krylov subspace was first proposed by Druskin and Knizhnerman in [11] to numerically approximate the action of a matrix function f(A) on a vector v where $A \in \mathbb {R}^{n \times n}$ is a symmetric matrix and $v \in \mathbb {R}^{n}$ and where the extended Krylov subspace was generated by means of the extended Arnoldi process. The method was then generalized to the non-symmetric case by Simoncini in [28] and applied for solving large-scale Lyapunov matrix equations [25, 28] with low rank right-hand sides. In [22], the authors used the extended block Arnoldi process for computing approximate solutions to large scale continuous-time algebraic Riccati equations. They also showed that this procedure still satisfies the well known Arnoldi recursions. Nowadays, the extended block Arnoldi algorithm becomes an efficient method for reducing the order of large scale MIMO dynamical systems; see [1] and references therein.

Let $V \in \mathbb {R}^{n \times p}$, the extended block Krylov subspace $\mathbb {K}_{m}^{e}(A,V)$ can be considered as the subspace of $\mathbb {R}^{n}$ spanned by the columns of the matrices $A^{k}V,~k=-m,\ldots ,m-1$, i.e.,

$$\begin{aligned} \mathbb {K}_{m}^{e}(A,V)=\mathrm{Range} \left\{ A^{-m}\,V,\ldots ,A^{-2}\,V,A^{-1}\,V,V,A\,V,A^{2}\,V,\ldots ,A^{m-1}\,V\right\} . \end{aligned}$$

It is clear that the subspace $\mathbb {K}_{m}^{e}(A,V)$ is a sum of two block Krylov subspaces. More precisely,

$$\begin{aligned} \mathbb {K}_{m}^e(A,V)=\mathbb {K}_{m}(A,V)+\mathbb {K}_{m}(A^{-1},A^{-1}\,V), \end{aligned}$$

where $\mathbb {K}_{m}(A,V)=\mathrm{Range} \lbrace V,~A\,V,~A^{2}\,V,~\ldots ,~A^{m-1}\,V \rbrace$ is the classical block Krylov subspace related to A and $\mathbb {K}_{m}(A^{-1},A^{-1}V)$ is related to the inverse of A. The use of the extended subspace $\mathbb {K}_{m}^{e}(A,V)$ is justified by the fact that it contains more information than the classical subspace $\mathbb {K}_{m}(A,V)$ since it is enriched by $A^{-1}$.

In this paper, we show how to derive a new algorithm called the extended block Lanczos algorithm. This process allows us to compute two biorthogonal matrices $\mathbb {V}_{2m}, \mathbb {W}_{2m} \in \mathbb {R}^{n \times 2mp}$ for the extended Krylov subspaces $\mathbb {K}_{m}^e(A,V)$ and $\mathbb {K}_{m}^e(A^{T},W)$, where $V, \, W \in \mathbb {R}^{n \times p}$. We also show that this algorithm satisfies a three-term recurrence, which is an advantage as compared to the extended Arnoldi algorithm. This is very important for storage requirements when the problem is large. However, the drawbacks of any Lanczos-based method is the use of $A^T$ and the possibility of a break-down. These could be overcome by using some techniques called look-ahead or transposee-free methods as described in [8, 10, 13]. Notice also that as for the extended Arnoldi process, we assume that the matrix A is nonsingular and when it is sparse and structured, the terms of the form $A^{-1}V$ are computed by the LU decomposition and when it is not the case, then one can use a preconditioned solver such as the GMRES method. Another aim of this paper is to show that the extended block Lanczos algorithm can be applied to model order reduction problems by combining it with moment matching techniques. More precisely, we show that the moments and the Markov parameters of the original transfer function are both approximated by those of the reduced transfer function.

The paper is organized as follows. In Sect. 2, we describe the extended block Lanczos algorithm and derive some new algebraic properties. The application of this process to model order reduction is considered in Sect. 3 where we show how to apply the extended block Lanczos process to Multiple-Input Multiple-Output (MIMO) dynamical systems in order to produce low-order dimensional systems. The last section is devoted to some numerical experiments.

2 The extended block Lanczos algorithm

Before describing the extended block Lanczos process, we have to describe the following procedure which, if applied to $\widehat{V}=[\hat{v}_1,\ldots ,\hat{v}_k],~ \widehat{W}=[\hat{w}_1,\ldots ,\hat{w}_k] \in \mathbb {R}^{n \times k}$, allows to obtain biorthogonal blocks$\widetilde{V},~ \widetilde{W} \in \mathbb {R}^{n \times k}$.

The above biorthogonalization procedure can be seen as a two-sided Gram–Schmidt process applied to the two sequences $\{\hat{v}_1,\ldots ,\hat{v}_k\}$ and $\{\hat{w}_1,\ldots ,\hat{w}_k\}$. A premature termination is possible at step i ($i < k$) if $\beta =0$ and this can occur in two ways:

• case (I) either $\hat{v}=0$ or $\hat{w} =0$ or both,

• case (II) $\beta = \hat{w}^T\,\hat{v}= 0$, even though $\hat{v} \ne 0$ and $\hat{w} \ne 0$.

Generally, the biorthogonalization procedure is applied within the Lanczos process with $\hat{v}_i=A^{i-1}\,\hat{v}_0$ and $\hat{w}_i={(A^T)}^{i-1}\,\hat{w}_0$ ($\hat{v}_0$ and $\hat{w}_0$ are given starting vectors). In this case, (I) is considered as a happy breakdown since it is related to the invariance of the Krylov subspace $K_i(A,\hat{v}_0)$ if $\hat{v}=0$ or to the invariance of the Krylov subspace $K_i(A^T,\hat{w}_0)$ if $\hat{w}=0$. The real trouble is (II), Wilkinson in [29] calls this a serious breakdown. For more details about the breakdown in the biorthogonalization procedure and its connection with the Lanczos process, we refer to [26, 29] and the references therein. If k iterations are performed, the above algorithm produces $\widetilde{V}=[\widetilde{v}_1,\ldots ,\widetilde{v}_k],~ \widetilde{W}=[\widetilde{w}_1,\ldots ,\widetilde{w}_k] \in \mathbb {R}^{n \times k}$ and $R=(r_{j,i}),~Z=(z_{j,i}) \in \mathbb {R}^{k \times k}$ upper triangular matrices such that $\widehat{V} = \widetilde{V}\,R$, $\widehat{W} = \widetilde{W}\,Z$, $\widetilde{W}^T\,\widetilde{V} = I_k$ and $I_k$ is the $k \times k$ identity matrix.

2.1 Description of the process

Let $A\in \mathbb {R}^{n \times n}$ and let V, W be two given initial blocks of $\mathbb {R}^{n \times p}$. In this section, we first introduce the extended block Lanczos process for constructing two biorthogonal bases $\mathbb {V}_{2m}$ and $\mathbb {W}_{2m}$ of the extended block Krylov subspaces $\mathbb {K}_{m}^{e}(A,V)$ and $\mathbb {K}_{m}^{e}(A^{T},W)$, respectively.

Let $\mathbb {V}_{2m}=\lbrace {\mathscr {V}}_{1},{\mathscr {V}}_{2},\ldots ,{\mathscr {V}}_{m} \rbrace$ and $\mathbb {W}_{2m}=\lbrace {\mathscr {W}}_{1},{\mathscr {W}}_{2},\ldots ,{\mathscr {W}}_{m} \rbrace$ where ${\mathscr {V}}_i, {\mathscr {W}}_i$, for $i=1,\ldots ,m$ be $n \times 2p$ matrices. Then $\mathbb {V}_{2m}$ and $\mathbb {W}_{2m}$ are biorthogonal if and only if the $n \times 2p$ matrices ${\mathscr {V}}_i$ and ${\mathscr {W}}_j$ satisfy the following biorthogonality condition

$$\begin{aligned} \left\{ \begin{array}{c c c} {\mathscr {W}}_{j}^{T}\,{\mathscr {V}}_{i}= 0_{2p}, \ \text{ if } \ i \ne j,\\ {\mathscr {W}}_{j}^{T}\,{\mathscr {V}}_{i}=I_{2p}, \ \text{ if } \ i = j.\\ \end{array} \right. \end{aligned}$$

Now, we describe the procedure that allows to compute the biorthogonal bases of the extended block Lanczos algorithm.

Initialization. Let us partition the two first matrices ${\mathscr {V}}_1$ and ${\mathscr {W}}_1$ of the extended block Lanczos process as ${\mathscr {V}}_{1}=[V_{1},V_{2}]$ and ${\mathscr {W}}_{1}=[W_{1},W_{2}]$ where each $V_i, W_i \in \mathbb {R}^{n \times p}$ for $i=1,2$. To obtain ${\mathscr {V}}_1$ and ${\mathscr {W}}_1$, we apply the biorthogonalization procedure (biorth) described by Algorithm 1 to the matrices $[V,~A^{-1}\,V]$ and $[W,~A^{-T}\,W]$ of $\mathbb {R}^{n \times 2p}$. We then get

$$\begin{aligned} {\left\{ \begin{array}{ll} {[}V,~A^{-1}\,V{]} &{}= {\mathscr {V}}_1\,\varLambda _V, \\ {[}W,~A^{-T}\,W{]} &{}= {\mathscr {W}}_1\,\varLambda _W ,\\ \end{array}\right. } \end{aligned}$$

(2)

where $\varLambda _V$ and $\varLambda _W$ are $2p \times 2p$ upper triangular matrices and ${\mathscr {V}}_1, {\mathscr {W}}_1$ are $n \times 2p$ biorthogonal matrices, i.e., ${\mathscr {W}}_1^T\,{\mathscr {V}}_1 = I_{2p}$.

Iteration k. We assume that ${\mathscr {V}}_1,\ldots ,{\mathscr {V}}_k$ and ${\mathscr {W}}_1,\ldots ,{\mathscr {W}}_k$ have been computed. Next, we seek for ${\mathscr {V}}_{k+1}, {\mathscr {W}}_{k+1} \in \mathbb {R}^{n \times 2p}$ under the form ${\mathscr {V}}_{k+1} = [V_{2k+1},~V_{2k+2}]$ and ${\mathscr {W}}_{k+1} = [W_{2k+1},~W_{2k+2}]$ where the block vectors $V_{2k+1},~W_{2k+1} \in \mathbb {R}^{n \times p}$ are computed by orthogonalizing the matrix-vector products $AV_{2k-1}$ and $A^{T}W_{2k-1}$ against $V_1, V_2,\ldots ,V_{2k}$ and $W_1,W_2,\ldots ,W_{2k}$ respectively, i.e., the matrices $V_{2k+1},W_{2k+1}$ are computed via

$$\begin{aligned} \left\{ \begin{array} {lcl} V_{2k+1}\,H_{2k+1,2k-1} &{}=&{}A\,V_{2k-1}-\displaystyle \sum _{i=1}^{2k}V_i \,H_{i,2k-1}, \\ W_{2k+1}\,G_{2k+1,2k-1} &{}=&{} A^T\,W_{2k-1}-\displaystyle \sum _{i=1}^{2k} W_i\,G_{i,2k-1},\, \end{array} \right. \end{aligned}$$

(3)

where the coefficients $H_{1,2k-1},\ldots ,~H_{2k,2k-1}$ and $G_{1,2k-1},\ldots ,~G_{2k,2k-1}$ are $p \times p$ matrices obtained respectively by imposing orthogonality conditions

$$\begin{aligned} V_{2k+1}~\bot ~[W_1,~W_2,\ldots ,~W_{2k}] \ \ \text{ and } \ \ W_{2k+1}~\bot ~[V_1,~V_2,\ldots ,~V_{2k}]. \end{aligned}$$

In this case, we have

$$\begin{aligned} H_{i,2k-1}=W_i^T\,A\,V_{2k-1} \ \ \text{ and } \ \ G_{i,2k-1}=V_i^T\,A^T\,W_{2k-1}, \ \ \text{ for } i=1,2,\ldots ,2k. \end{aligned}$$

Similarly, the matrices $V_{2k+2},~W_{2k+2} \in \mathbb {R}^{n \times p}$ are computed by orthogonalizing the matrix-vector products $A^{-1}\, V_{2k}$ and $A^{-T}\,W_{2k}$ against $V_1,~V_2,\ldots ,~V_{2k+1}$ and $W_1,~W_2,\ldots ,~W_{2k+1}$ respectively, i.e., we generate the vectors $V_{2k+2},~W_{2k+2}$ satisfying :

$$\begin{aligned} \left\{ \begin{array} {lcl} V_{2k+2}\,H_{2k+2,2k}&{}=&{}A^{-1}\,V_{2k}-\displaystyle \sum _{i=1}^{2k+1} V_i\,H_{i,2k}, \\ W_{2k+2}\,G_{2k+2,2k} &{}=&{} (A^T)^{-1}\,W_{2k}-\displaystyle \sum _{i=1}^{2k+1} W_i\,G_{i,2k}, \end{array} \right. \end{aligned}$$

(4)

where again imposing the orthogonality conditions

$$\begin{aligned} V_{2k+2}~\bot ~W_1,\ldots ,~W_{2k+1} \quad \text{ and } \quad W_{2k+2}~\bot ~V_1,\ldots ,~V_{2k+1}, \end{aligned}$$

we easily verify that the $p \times p$ coefficient matrices $H_{1,2k},\ldots ,~H_{2k+1,2k}$ and $G_{1,2k},\ldots ,~G_{2k+1,2k}$, are respectively given by :

$$\begin{aligned} H_{i,2k}=W_i^T\,A^{-1}\,V_{2k} \ \ \text{ and } \ \ G_{i,2k}=V_i^T\,(A^T)^{-1}\,W_{2k}, \text{ for } i=1,2,\ldots ,2k+1. \end{aligned}$$

The coefficients $H_{2k+1,2k-1}$ and $G_{2k+1,2k-1}$ are $p \times p$ matrices that normalize the matrices $V_{2k+1}$ and $W_{2k+1}$ while $H_{2k+2,2k}$ and $G_{2k+2,2k}$ are $p \times p$ matrices that normalize the matrices $V_{2k+2}$ and $W_{2k+2}$. The extended block Lanczos process described above allows to compute two biorthogonal matrices $\mathbb {V}_{2m+2}=[{\mathscr {V}}_{1},\ldots ,~{\mathscr {V}}_{m+1}]$ and $\mathbb {W}_{2m+2}=[{\mathscr {W}}_{1},\ldots ,~{\mathscr {W}}_{m+1}]$, such that ${\mathscr {V}}_{k}=[V_{2k-1},~V_{2k}]$ and ${\mathscr {W}}_{k}=[W_{2k-1},~W_{2k}]$ for $k=1,\ldots ,m+1$.

This algorithm constructs also two $2(m+1)p \times 2mp$ upper block Hessenberg matrices $\widetilde{\mathbb {H}}_{2m}=[H_{i,j}]$ and $\widetilde{\mathbb {G}}_{2m}=[G_{i,j}]$, where $H_{i,j},~G_{i,j} \in \mathbb {R}^{p \times p}$ for $i=1,\ldots ,2m+2, j=1,\ldots ,2m$.

Next, we give some properties for the biorthogonal matrices $\mathbb {V}_{2m+2},~\mathbb {W}_{2m+2}$, and the upper block Hessenberg matrices $\mathbb {\widetilde{H}}_{2m},~ \mathbb {\widetilde{G}}_{2m}$. We consider the following notation:

• $\mathbb {V}^{o}_{m}$ and $\mathbb {W}^{o}_{m}$ are matrices of $\mathbb {R}^{n \times mp}$ formed by the block columns of odd indices of the matrices $\mathbb {V}_{2m}$ and $\mathbb {W}_{2m}$, respectively.

• $\mathbb {V}^{e}_{m}$ and $\mathbb {W}^{e}_{m}$ are the matrices formed by the block columns of even indices of the bases $\mathbb {V}_{2m}$ and $\mathbb {W}_{2m}$, respectively.

• $\mathbb {H}^{o}_{m}$ and $\mathbb {G}^{o}_{m}$ are the matrices of $\mathbb {R}^{(2m+1)p \times mp}$ formed by the block columns of odd indices of the matrices $\widetilde{\mathbb {H}}_{2m}$ and $\widetilde{\mathbb {G}}_{2m}$, respectively.

• $\mathbb {H}^{e}_{m}$ and $\mathbb {G}^{e}_{m}$ are the matrices of $\mathbb {R}^{2(m+1)p \times mp}$ formed by the block columns of even indices of the matrices $\widetilde{\mathbb {H}}_{2m}$ and $\widetilde{\mathbb {G}}_{2m}$, respectively.

• $\mathbb {{\widehat{H}}}^{o}_{m}$ and $\mathbb {{\widehat{G}}}^{o}_{m}$ correspond to the block columns and the block rows of odd indices of the matrices $\mathbb {H}_{2m}=[H_{i,j}]_{i=1,\ldots ,2m}^{j=1,\ldots ,2m}$ and $\mathbb {G}_{2m}=[G_{i,j}]_{i=1,\ldots ,2m}^{j=1,\ldots ,2m}$, respectively.

• $\mathbb {{\breve{H}}}^{e}_{m}$ and $\mathbb {{\breve{G}}}^{e}_{m}$ are formed by the block columns and the block row of even indices of $\mathbb {H}_{2m}$ and $\mathbb {G}_{2m}$, respectively.

We have the following result.

Proposition 1

Using the above notation, and letting $\mathbb {V}_{2m+1}=[\mathbb {V}_{2m},~{ \mathscr {V}}_{2m+1}]$ and $\mathbb {W}_{2m+1}=[\mathbb {W}_{2m},~{\mathscr {W}}_{2m+1}]$, then, we have

$$\begin{aligned} A \, \mathbb {V}^{o}_{m}= & {} \mathbb {V}_{2m+1} \, \mathbb {H}^{o}_{m}, \end{aligned}$$

(5)

$$\begin{aligned} A^{T} \, \mathbb {W}^{o}_{m}= & {} \mathbb {W}_{2m+1} \, \mathbb {G}^{o}_{m}, \end{aligned}$$

(6)

$$\begin{aligned} A^{-1} \, \mathbb {V}^{e}_{m}= & {} \mathbb {V}_{2m+2} \, \mathbb {H}^{e}_{m}, \end{aligned}$$

(7)

$$\begin{aligned} A^{-T} \, \mathbb {W}^{e}_{m}= & {} \mathbb {W}_{2m+2} \, \mathbb {G}^{e}_{m}. \end{aligned}$$

(8)

Furthermore, the matrices $\mathbb {H}_{2m}$ and $\mathbb {G}_{2m}$ are $2p \times 2p$ tridiagonal matrices.

Proof

Equations (5)–(8) can be easily proven by considering the relations (3) and (4), for $k=1,\ldots ,m$, and the biorthogonality condition.

Now, using Eqs.  (5) and (6), and the biorthogonality condition, we get

$$\begin{aligned} (\mathbb {W}^{o}_{m})^{T}\,A \mathbb {V}^{o}_{m} = (\mathbb {W}^{o}_{m})^{T} \, \mathbb {V}_{2m+1} \, \mathbb {H}^{o}_{m} = \mathbb {{\widehat{H}}}^{o}_{m}, \end{aligned}$$

and

$$\begin{aligned} (\mathbb {V}^{o}_{m})^{T}\,A^{T} \mathbb {W}^{o}_{m} =(\mathbb {V}^{o}_{m})^{T} \, \mathbb {W}_{2m+1} \, \mathbb {G}^{o}_{m} = \mathbb {{\widehat{G}}}^{o}_{m}, \end{aligned}$$

which gives

$$\begin{aligned} \mathbb {{\widehat{H}}}^{o}_{m}=(\mathbb {{\widehat{G}}}^{o}_{m})^{T}. \end{aligned}$$

(9)

In the same manner, we can use Eqs. (7) and (8) to show that

$$\begin{aligned} \mathbb {{\breve{H}}}^{e}_{m}=(\mathbb {{\breve{G}}}^{e}_{m})^{T}. \end{aligned}$$

(10)

Comparing the members of equalities (9) and (10), we note that the first member in both equalities is an upper block Hessenberg matrix while the second is a lower block Hessenberg matrix . Then, $\mathbb {{\widehat{H}}}^{o}_{m}, \mathbb {{\widehat{G}}}^{o}_{m}, \mathbb {{\breve{H}}}^{e}_{m}$ and $\mathbb {{\breve{G}}}_{m}^{e}$ are $p \times p$ tridiagonal matrices. Therefore, $\mathbb {H}_{2m}$ and $\mathbb {G}_{2m}$ are $2p \times 2p$ tridiagonal matrices. $\square$

Using the fact that $\mathbb {H}_{2m}$ and $\mathbb {G}_{2m}$ are $2p \times 2p$ tridiagonal matrices and that the sub-diagonal blocks are $2p \times 2p$ upper triangular matrices, the relations given in (3) and (4) can be simplified as

$$\begin{aligned} V_{2k+1} \, H_{2k+1,2k-1}= & {} A \, V_{2k-1} -V_{2k-3}\, H_{2k-3,2k-1} - V_{2k-2}\,H_{2k-2,2k-1} \nonumber \\&- V_{2k-1}\,H_{2k-1,2k-1} - V_{2k}\, H_{2k,2k-1} \end{aligned}$$

(11)

$$\begin{aligned} W_{2k+1}\,G_{2k+1,2k-1}= & {} A^T \, W_{2k-1} -W_{2k-3}\, G_{2k-3,2k-1} - W_{2k-2}\, G_{2k-2,2k-1} \nonumber \\&- W_{2k-1}\,G_{2k-1,2k-1} - W_{2k}\, G_{2k,2k-1}, \end{aligned}$$

(12)

and

$$\begin{aligned} V_{2k+2}\,H_{2k+2,2k}= & {} A^{-1} \, V_{2k} - V_{2k-2}\,H_{2k-2,2k} -V_{2k-1}\,H_{2k-1,2k} \nonumber \\&- V_{2k}\,H_{2k,2k} -V_{2k+1}\,H_{2k+1,2k} \end{aligned}$$

(13)

$$\begin{aligned} W_{2k+2}G_{2k+2,2k}= & {} (A^T)^{-1} \, W_{2k} -\,W_{2k-2} G_{2k-2,2k}- W_{2k-1}G_{2k-1,2k} \nonumber \\&- W_{2k}G_{2k,2k} - W_{2k+1}G_{2k+1,2k}. \end{aligned}$$

(14)

Now, we write Eqs.  (11)–(14) in the following form

$$\begin{aligned}{}[V_{2k+1} \ V_{2k+2}]\left( \begin{array}{cc} H_{2k+1,2k-1} &{} H_{2k+1,2k} \\ 0 &{} H_{2k+2,2k} \end{array}\right)= & {} [AV_{2k-1} \ A^{-1}V_{2k}] \nonumber \\- & {} [V_{2k-1} \ V_{2k}]\left( \begin{array}{cc} H_{2k-1,2k-1} &{} H_{2k-1,2k} \\ H_{2k,2k-1} &{} H_{2k,2k} \end{array}\right) \nonumber \\- & {} [V_{2k-3} \ V_{2k-2}]\left( \begin{array}{cc} H_{2k-3,2k-1} &{} 0 \\ H_{2k-2,2k-1} &{} H_{2k-2,2k} \end{array}\right) ,\nonumber \\ \end{aligned}$$

(15)

and

$$\begin{aligned}{}[W_{2k+1} \ W_{2k+2}]\left( \begin{array}{cc} G_{2k+1,2k-1} &{} G_{2k+1,2k} \\ 0 &{} G_{2k+2,2k} \end{array}\right)= & {} \left[ A^{T}W_{2k-1} \ A^{-T}W_{2k}\right] \nonumber \\ \nonumber- & {} [W_{2k-1} \ W_{2k}]\left( \begin{array}{cc} G_{2k-1,2k-1} &{} G_{2k-1,2k} \\ G_{2k,2k-1} &{} G_{2k,2k} \end{array}\right) \nonumber \\- & {} [W_{2k-3} \ W_{2k-2}]\left( \begin{array}{cc} G_{2k-3,2k-1} &{} 0 \\ G_{2k-2,2k-1} &{} G_{2k-2,2k} \end{array}\right) .\nonumber \\ \end{aligned}$$

(16)

Let

$$\begin{aligned} \left\{ \begin{array}{lll} { \mathscr {V}}_{k-1}=[V_{2k-3} \ V_{2k-2}], \, {\mathscr {V}}_{k}=[V_{2k-1} \ V_{2k}], \, {\mathscr {V}}_{k+1}=[V_{2k+1} \ V_{2k+2}] \\ \\ { \mathscr {W}}_{k-1}=[W_{2k-3} \ W_{2k-2}], \, { \mathscr {W}}_{k}=[W_{2k-1} \ W_{2k}], \,{ \mathscr {W}}_{k+1}=[W_{2k+1} \ W_{2k+2}] \\ \\ \ U_{k+1}=[AV_{2k-1} \ A^{-1}V_{2k}], \, S_{k+1}=[A^{T}W_{2k-1} \ A^{-T}W_{2k}] \end{array} \right. \end{aligned}$$

and

$$\begin{aligned} \left\{ \begin{array}{lll} N_{k}=\left( \begin{array}{cc} H_{2k-3,2k-1} &{} 0 \\ H_{2k-2,2k-1} &{} H_{2k-2,2k} \end{array}\right) , \,\, \widetilde{N}_{k}=\left( \begin{array}{cc} G_{2k-3,2k-1} &{} 0\\ G_{2k-2,2k-1} &{} G_{2k-2,2k} \end{array}\right) \\ \\ C_{k}=\left( \begin{array}{cc} H_{2k-1,2k-1} &{} H_{2k-1,2k} \\ H_{2k,2k-1} &{} H_{2k,2k} \end{array}\right) , \,\, \widetilde{C}_{k}=\left( \begin{array}{cc} G_{2k-1,2k-1} &{} G_{2k-1,2k} \\ G_{2k,2k-1} &{} G_{2k,2k} \end{array}\right) \\ \\ A_{k+1}=\left( \begin{array}{cc} H_{2k+1,2k-1} &{} H_{2k+1,2k} \\ 0 &{} H_{2k+2,2k} \end{array}\right) , \,\, \widetilde{A}_{k+1}=\left( \begin{array}{cc} G_{2k+1,2k-1} &{} G_{2k+1,2k} \\ 0 &{} G_{2k+2,2k} \end{array}\right) \end{array} \right. \end{aligned}$$

Therefore, Eqs. (15) and (16) can be written as

$$\begin{aligned} \left\{ \begin{array}{l} {\mathscr {V}}_{k+1}\, A_{k+1}=U_{k+1}-{\mathscr {V}}_{k}\,C_{k}-{\mathscr {V}}_{k-1}\,N_{k},\\ \\ {\mathscr {W}}_{k+1}\, \widetilde{A}_{k+1}=S_{k+1}-{\mathscr {W}}_{k}\,\widetilde{C}_{k}-{\mathscr {W}}_{k-1}\,\widetilde{N}_{k}. \end{array} \right. \end{aligned}$$

Finally, the extended block Lanczos algorithm is summarized as follows.

At each step of Algorithm 2, we need to compute $A^{-1}\,V_{2k}$ and $A^{-T}\,W_{2k}$. For large and structured matrices, we use the LU factorization while for non-structured problems, we can use solvers such as GMRES with a preconditioner.

We notice that there may be a breakdown during the kth iteration of the extended block Lanczos process as described by Algorithm 2 when either one of the matrices $A_{k+1}$ or ${\widetilde{A}}_{k+1}$ is singular. The matrix $A_{k+1}$ -or ${\widetilde{A}}_{k+1}$- being triangular, is itself singular if one of the two diagonal coefficients $H_{2k+1,2k-1}$ or $H_{2k+2,2k}$ -$G_{2k+1,2k-1}$ or $G_{2k+ 2,2k}$- is singular. Such breakdown can be treated via look-ahead or deflation techniques similar to what has been applied for the classical block Lanczos process, see [2, 4, 8, 10, 13] and the references therein. Deflation techniques and look-ahead strategies are not easy to implement and require a detailed study and this not done in the present paper.

In the sequel, we assume that there is no breakdown. In this case, after m steps, Algorithm 2 builds two biorthogonal bases $\mathbb {V}_{2m+2}$ and $\mathbb {W}_{2m+2}$ and two $2(m+1)p \times 2mp$ upper block Hessenberg matrices $\widetilde{\mathbb {H}}_{2m}$ and $\widetilde{\mathbb {G}}_{2m}$ defined as follows

$$\begin{aligned} \widetilde{\mathbb {H}}_{2m}=\left[ \begin{array}{c} \mathbb {H}_{2m} \\ \\ A_{m+1}\,E_{m}^{T}\\ \end{array}\right] \ \ \ \text{ and } \ \ \ \widetilde{\mathbb {G}}_{2m}=\left[ \begin{array}{c} \mathbb {G}_{2m} \\ \\ \widetilde{A}_{m+1}\,E_{m}^{T}\\ \end{array}\right] , \end{aligned}$$

where

$$\begin{aligned} \mathbb {H}_{2m}=\left( \begin{array}{ccccc} C_{1} &{} N_{1}&{} &{} \\ A_{2} &{} C_{2} &{} \ddots &{} \\ &{} \ddots &{} \ddots &{} N_{m-1} \\ &{} &{} A_{m}&{} C_{m} \end{array} \right) \ \ \text{ and } \ \ \mathbb {G}_{2m}=\left( \begin{array}{ccccc} \widetilde{C}_{1} &{} \widetilde{N}_{1}&{} &{} \\ \widetilde{A}_{2} &{} \widetilde{C}_{2} &{} \ddots &{} \\ &{} \ddots &{} \ddots &{} \widetilde{N}_{m-1} \\ &{} &{} \widetilde{A}_{m}&{} \widetilde{C}_{m} \end{array} \right) . \end{aligned}$$

(17)

2.2 Theoretical results

In this subsection, we derive some theoretical results about the extended block Lanczos Algorithm. Let $\mathbb {T}_{2m}=\mathbb {W}_{2m}^{T}\,A\,\mathbb {V}_{2m} \in \mathbb {R}^{2mp \times 2mp}$. Using the same technique as in [28] (for the extended block Arnoldi process), we can easily verified that $\mathbb {T}_{2m}$ is block upper Hessenberg with $2p \times 2p$ blocks. In the following, we will also consider the $2mp \times 2mp$ matrix defined as

$$\begin{aligned} \mathbb {L}_{2m} = \mathbb {W}_{2m}^{T}\,A^{-1}\,\mathbb {V}_{2m}. \end{aligned}$$

Notice that we can check that $\mathbb {L}_{2m}$ is also a $2p \times 2p$ block upper Hessenberg matrix.

Proposition 2

Suppose that m steps of Algorithm 2 have been carried out and let $\widetilde{\mathbb {T}}_{2m}=\mathbb {W}_{2m+2}^{T}\,A\,\mathbb {V}_{2m}$ and $\widetilde{\mathbb {L}}_{2m}=\mathbb {W}_{2m+2}^{T}\,A^{-1}\,\mathbb {V}_{2m}$. Then, the following relations hold

$$\begin{aligned} A \,\mathbb {V}_{2m}= & {} \mathbb {V}_{2m} \,\mathbb {T}_{2m}+{\mathscr {V}}_{m+1}\,T_{m+1,m}\,E_{m}^{T} \end{aligned}$$

(18)

$$\begin{aligned} A^{-1} \, \mathbb {V}_{2m}= & {} \mathbb {V}_{2m} \, \mathbb {L}_{2m}+{\mathscr {V}}_{m+1}\,L_{m+1,m}\,E_{m}^{T} \end{aligned}$$

(19)

$$\begin{aligned} A^{T} \, \mathbb {W}_{2m}= & {} \mathbb {W}_{2m} \, \mathbb {T}^{T}_{2m}+{\mathscr {W}}_{m+1}\,\widetilde{T}_{m+1,m}\,E_{m}^{T} \end{aligned}$$

(20)

$$\begin{aligned} A^{-T} \,\mathbb {W}_{2m}= & {} \mathbb {W}_{2m}\, \mathbb {L}^{T}_{2m}+{\mathscr {W}}_{m+1}\,\widetilde{L}_{m+1,m}\,E_{m}^{T}, \end{aligned}$$

(21)

where $\widetilde{T}_{m+1,m}={\mathscr {V}}_{m+1}^{T}\,A^{T}\,\mathbb {W}_{2m}$, $\widetilde{L}_{m+1,m}={\mathscr {V}}_{m+1}^{T}\,A^{-T}\,\mathbb {W}_{2m}$ and $E_m$ is the last $2mp \times 2p$ block of the identity matrix $I_{2mp}$.

Proof

To prove the first relation, we start by using the fact that $A\,\mathbb {K}^{e}_{m}(A,V) \subseteq \mathbb {K}^{e}_{m+1}(A,V)$, and the biorthogonality condition. Then, there exists a matrix T such that $A\,\mathbb {V}_{2m} = \mathbb {V}_{2m+2}\,T$. Hence $T=\mathbb {W}_{2m+2}^{T}\,A\,\mathbb {V}_{2m}$ which gives $T = \widetilde{\mathbb {T}}_{2m}$. Therefore

$$\begin{aligned} A\, \mathbb {V}_{2m} = \mathbb {V}_{2m+2}\, \widetilde{\mathbb {T}}_{2m}. \end{aligned}$$

Now, since we have $\mathbb {V}_{2m+2}=[\mathbb {V}_{2m}, {\mathscr {V}}_{m+1}], \mathbb {W}_{2m+2}=[\mathbb {W}_{2m}, {\mathscr {W}}_{m+1}]$ and as $\mathbb {T}_{2m+2}=\mathbb {W}_{2m+2}^{T}\,A\,\mathbb {V}_{2m+2}$ is block upper Hessenberg matrix, then

$$\begin{aligned} T_{m+1,m}\,E_{m}^{T}={\mathscr {W}}_{m+1}^{T}\,A\,\mathbb {V}_{2m}. \end{aligned}$$

Hence

$$\begin{aligned} \widetilde{\mathbb {T}}_{2m}=\mathbb {W}_{2m+2}^{T}\,A\,\mathbb {V}_{2m}=\left[ \begin{array}{c} \mathbb {T}_{2m} \\ {\mathscr {W}}_{m+1}^{T}\,A\,\mathbb {V}_{2m}\\ \end{array}\right] =\left[ \begin{array}{c} \mathbb {T}_{2m} \\ T_{m+1,m}\,E_{m}^{T}\\ \end{array}\right] \end{aligned}$$

which completes the proof of (18).

For the second relation, we follow the same procedure. As $\mathbb {L}_{2m+2}=\mathbb {W}_{2m+2}^{T}\,A^{-1}\mathbb {V}_{2m+2}$ is block upper Hessenberg matrix, we have

$$\begin{aligned} {\mathscr {W}}_{m+1}^{T}\, A^{-1} \,\mathbb {V}_{2m}=L_{m+1,m}\,E_{m}^{T}, \end{aligned}$$

and then the upper block Hessenberg matrix $\widetilde{\mathbb {L}}_{2m}$ can be written as

$$\begin{aligned} \widetilde{\mathbb {L}}_{2m}=\mathbb {W}_{2m+2}^{T}\, A^{-1}\,\mathbb {V}_{2m}=\left[ \begin{array}{c} \mathbb {L}_{2m} \\ {\mathscr {W}}_{m+1}^{T} \,A^{-1}\,\mathbb {V}_{2m}\\ \end{array}\right] =\left[ \begin{array}{c} \mathbb {L}_{2m} \\ L_{m+1,m}\,E_{m}^{T}\\ \end{array}\right] . \end{aligned}$$

Using the biorthogonality condition and the fact that $A^{-1}\,\mathbb {K}^{e}_{m}(A,V) \subseteq \mathbb {K}^{e}_{m+1}(A,V)$, then there exists a matrix L such that

$$\begin{aligned} A^{-1}\,\mathbb {V}_{2m} = \mathbb {V}_{2m+2}\,L. \end{aligned}$$

Hence

$$\begin{aligned} L=\mathbb {W}_{2m+2}^{T}\,A^{-1}\,\mathbb {V}_{2m}, \end{aligned}$$

which gives

$$\begin{aligned} L = \widetilde{\mathbb {L}}_{2m}. \end{aligned}$$

Therefore

$$\begin{aligned} A^{-1} \,\mathbb {V}_{2m} = \mathbb {V}_{2m+2}\,\widetilde{\mathbb {L}}_{2m}= \mathbb {V}_{2m}\, \mathbb {L}_{2m}+{\mathscr {V}}_{m+1}\,L_{m+1,m}\,E_{m}^{T} . \end{aligned}$$

In a similar way, we can use the following relations $A^{T}\,\mathbb {K}^{e}_{m}(A^{T},W) \subseteq \mathbb {K}^{e}_{m+1}(A^{T},W)$ and $A^{-T}\,\mathbb {K}^{e}_{m}(A^{T},W) \subseteq \mathbb {K}^{e}_{m+1}(A^{T},W)$ to prove the assertion (20) and (21), respectively. $\square$

Let $\widetilde{\mathbb {T}}_{2m}$ and $\widetilde{\mathbb {H}}_{2m}$ be the block upper Hessenberg matrices defined earlier. The computation of $\widetilde{\mathbb {T}}_{2m}$ seems to require additional matrix-vector products with A and extra inner products of n-length vectors. To completely avoids this expensive step, we next derive recursions to compute the block columns of the matrices $\widetilde{\mathbb {T}}_{2m}$ directly from the block columns of the upper block Hessenberg matrix $\widetilde{\mathbb {H}}_{2m}$ without requiring the computation of matrix-vector products with A. We start by defining the following notation which will be used later.

• 1. For $k=1,\ldots ,m$, we partition ${\mathscr {V}}_{k}$ and ${\mathscr {W}}_{k}$ as

  $$\begin{aligned} {\mathscr {V}}_{k}=[{\mathscr {V}}_{k}^{(1)},{\mathscr {V}}_{k}^{(2)}] \;\;\; \text{ and } \;\;\; {\mathscr {W}}_{k}=[{\mathscr {W}}_{k}^{(1)},{\mathscr {W}}_{k}^{(2)}], \end{aligned}$$

  where ${\mathscr {V}}_{k}^{(1)}$ and ${\mathscr {W}}_{k}^{(1)}$ correspond to the first p columns of ${\mathscr {V}}_{k}$ and ${\mathscr {W}}_{k}$ respectively and ${\mathscr {V}}_{k}^{(2)}$, ${\mathscr {W}}_{k}^{(2)}$ correspond to the last p columns of ${\mathscr {V}}_{k}$, ${\mathscr {W}}_{k}$ respectively.

• 2. For $k=1,\ldots ,m$, we partition the upper triangular matrix $A_{k+1} \in \mathbb {R}^{2p \times 2p}$, computed from Algorithm 2, as

  $$\begin{aligned} A_{k+1}=\left[ \begin{array}{cc} A_{k+1}^{(1,1)} &{} A_{k+1}^{(1,2)}\\ 0 &{} A_{k+1}^{(2,2)} \end{array}\right] , \;\; \text{ where } A_{k+1}^{(i,j)} \in \mathbb {R}^{p \times p}. \end{aligned}$$

• 3. Let $\mathbb {H}_{2m}$ be the $2mp \times 2mp$ block upper Hessenberg matrix defined in (17) and ${\widetilde{e}}_i=e_i \otimes I_p$ where $e_i$ is the i-th vector of the canonical basis. From Algorithm 2, we have

  $$\begin{aligned} U_{m+1}=[U_{m+1}^{(1)},U_{m+1}^{(2)}]=[A\,{\mathscr {V}}_{m}^{(1)},A^{-1}\,{\mathscr {V}}_{m}^{(2)}]-\mathbb {V}_{2m}\,\mathbb {H}_{2m}\,[{\widetilde{e}}_{2k-1},{\widetilde{e}}_{2k}] \end{aligned}$$

  (22)

  and

  $$\begin{aligned} U_{m+1}={\mathscr {V}}_{m+1}\,A_{m+1}, \end{aligned}$$

  (23)

  which gives

  $$\begin{aligned} {\mathscr {V}}_{m+1}=U_{m+1}\,A_{m+1}^{-1}, \end{aligned}$$

  (24)

  where $A_{m+1}^{-1}$ is also a $2p \times 2p$ upper triangular matrix.

Proposition 3

Let $\widetilde{\mathbb {H}}_{2m}=[H_{i,j}]$ be the $2(m+1)p \times 2mp$ upper block Hessenberg matrix constructed by the extended block Lanczos algorithm and let $\widetilde{\mathbb {T}}_{2m}=\mathbb {W}_{2m+2}^{T}\,A\,\mathbb {V}_{2m}$. Then, for $k=1$

$$\begin{aligned} \widetilde{\mathbb {T}}_{2m}{\widetilde{e}}_{1}= & {} \widetilde{\mathbb {H}}_{2m}{\widetilde{e}}_{1} \nonumber \\ \mathbb {\widetilde{T}}_{2m}{\widetilde{e}}_{2}= & {} [{\widetilde{e}}_{1}\varLambda _{V}^{(1,1)}-\mathbb {\widetilde{H}}_{2m}{\widetilde{e}}_{1}\varLambda _{V}^{(1,2)}](\varLambda _{V}^{(2,2)})^{-1}. \end{aligned}$$

(25)

While for $k=2,\ldots ,m$

$$\begin{aligned} \widetilde{\mathbb {T}}_{2m}{\widetilde{e}}_{2k-1}= & {} \widetilde{\mathbb {H}}_{2m}{\widetilde{e}}_{2k-1},\\ \widetilde{\mathbb {T}}_{2m} {\widetilde{e}}_{2k}= & {} \mathbb {\widetilde{T}}_{2m}{\widetilde{e}}_{2k-1}\chi ^{(k)} + \left( {\widetilde{e}}_{2k-2}-\left[ \begin{array}{c} \mathbb {\widetilde{T}}_{2k-2}\\ 0_{2(m-k+1)p \times (2k-2)p}\\ \end{array}\right] \mathbb {H}_{2k-2}{\widetilde{e}}_{2k-2}\right) (A_{k}^{-1})^{(2,2)}, \end{aligned}$$

where

$$\begin{aligned} \chi ^{(k)}=A_{k}^{(1,1)}(A_{k}^{-1})^{(1,2)}. \end{aligned}$$

Proof

To prove the equalities for odd block columns, we start by considering relations (22) and (23) to get

$$\begin{aligned} A\,{\mathscr {V}}_{k}^{(1)}= & {} U_{k+1}\, {\widetilde{e}}_{1}+\mathbb {V}_{2k}\,\mathbb {H}_{2k}\,{\widetilde{e}}_{2k-1} \nonumber \\= & {} {\mathscr {V}}_{k+1}\,A_{k+1}\,{\widetilde{e}}_{1}+\mathbb {V}_{2k}\,\mathbb {H}_{2k}\,{\widetilde{e}}_{2k-1} \nonumber \\= & {} \mathbb {V}_{2k+2} \,\widetilde{\mathbb {H}}_{2k} \,{\widetilde{e}}_{2k-1}. \end{aligned}$$

Pre-multiplying the above equality by $\mathbb {W}_{2m+2}^{T}$, then

$$\begin{aligned} \mathbb {W}_{2m+2}^{T}\,A\,{\mathscr {V}}_{k}^{(1)}=\left[ \begin{array}{c} I_{2(k+1)p}\\ 0_{2(m-k)p \times 2(k+1)p}\\ \end{array}\right] \,\widetilde{\mathbb {H}}_{2k} \,{\widetilde{e}}_{2k-1}, \end{aligned}$$

hence

$$\begin{aligned} \widetilde{\mathbb {T}}_{2m}\, {\widetilde{e}}_{2k-1}=\left[ \begin{array}{c} \widetilde{\mathbb {H}}_{2k}\\ 0_{2(m-k)p \times 2kp}\\ \end{array}\right] \,{\widetilde{e}}_{2k-1}=\widetilde{\mathbb {H}}_{2m}\,{\widetilde{e}}_{2k-1}. \end{aligned}$$

To prove (25), we use the first equality in (2)

$$\begin{aligned}{}[V,A^{-1}\,V]=V_{1} \varLambda _V= & {} [{\mathscr {V}}_{1}^{(1)},{\mathscr {V}}_{1}^{(2)}] \left[ \begin{array}{cc} \varLambda _{V}^{(1,1)} &{} \varLambda _{V}^{(1,2)}\\ 0 &{} \varLambda _{V}^{(2,2)} \end{array}\right] \nonumber \\= & {} [{\mathscr {V}}_{1}^{(1)}\, \varLambda _{V}^{(1,1)},{\mathscr {V}}_{1}^{(1)} \,\varLambda _{V}^{(1,2)}+{\mathscr {V}}_{1}^{(2)} \varLambda _{V}^{(2,2)}]. \end{aligned}$$

(26)

If $\varLambda _{V}^{(1,1)}$ and $\varLambda _{V}^{(2,2)}$ are nonsingular, we obtain

$$\begin{aligned} A^{-1}\,{\mathscr {V}}_{1}^{(1)}=A^{-1}V\,(\varLambda _{V}^{(1,1)})^{-1}=[{\mathscr {V}}_{1}^{(1)}\,\varLambda _{V}^{(1,2)}+{\mathscr {V}}_{1}^{(2)} \,\varLambda _{V}^{(2,2)}]\,(\varLambda _{V}^{(1,1)})^{-1}, \end{aligned}$$

then

$$\begin{aligned} A\,{\mathscr {V}}_{1}^{(2)}=[{\mathscr {V}}_{1}^{(1)}\,\varLambda _{V}^{(1,1)}-A\,{\mathscr {V}}_{1}^{(1)}\,\varLambda _{V}^{(1,2)}]\,(\varLambda _{V}^{(2,2)})^{-1}. \end{aligned}$$

Pre-multiplying by $\mathbb {W}_{2m+2}$ to get equation (25).

For the other even block columns, we proceed as follows. From (22), we have

$$\begin{aligned} A\,U_{k+1}^{(2)}={\mathscr {V}}_{k}^{(2)}-A\, \mathbb {V}_{2k}\,\mathbb {H}_{2k}\,{\widetilde{e}}_{2k}, \end{aligned}$$

hence

$$\begin{aligned} \mathbb {W}_{2m+2}^{T}\,A\,U_{k+1}^{(2)}= & {} \mathbb {W}_{2m+2}^{T}\, {\mathscr {V}}_{k}^{(2)}-\mathbb {W}_{2m+2}^{T} \,A\, \mathbb {V}_{2k}\mathbb {H}_{2k}\,{\widetilde{e}}_{2k} \nonumber \\= & {} {\widetilde{e}}_{2k} - \left[ \begin{array}{c} \mathbb {\widetilde{T}}_{2k}\\ 0_{2(m-k)p \times 2kp}\\ \end{array}\right] \mathbb {H}_{2k}{\widetilde{e}}_{2k}. \end{aligned}$$

(27)

On the other hand, we use (24) to get

$$\begin{aligned} {\mathscr {V}}_{k+1}^{(2)}=U_{k+1}^{(1)}\,(A_{k+1}^{-1})^{(1,2)} +U_{k+1}^{(2)}\,(A_{k+1}^{-1})^{(2,2)}. \end{aligned}$$

We multiply the last equation on the left by A, and then we use (23) to obtain

$$\begin{aligned} A\,{\mathscr {V}}_{k+1}^{(2)}= & {} A\,U_{k+1}^{(1)}\,(A_{k+1}^{-1})^{(1,2)}+A\,U_{k+1}^{(2)} \,(A_{k+1}^{-1})^{(2,2)} \nonumber \\= & {} A\,{\mathscr {V}}_{k+1}^{(1)}\,A_{k+1}^{(1,1)}\, (A_{k+1}^{-1})^{(1,2)}+A\,U_{k+1}^{(2)}\,(A_{k+1}^{-1})^{(2,2)}. \end{aligned}$$

We pre-multiply by $\mathbb {W}_{2m+2}^{T}$ and we use (27) to get

$$\begin{aligned} \mathbb {W}_{2m+2}^{T}\,A\,{\mathscr {V}}_{k+1}^{(2)}= & {} \mathbb {W}_{2m+2}^{T}\, A\,{\mathscr {V}}_{k+1}^{(1)}\,A_{k+1}^{(1,1)}\,(A_{k+1}^{-1})^{(1,2)}\\&+\left( {\widetilde{e}}_{2k} - \left[ \begin{array}{c} \mathbb {\widetilde{T}}_{2k}\\ 0_{2(m-k)p \times 2kp}\\ \end{array}\right] \,\mathbb {H}_{2k}\,{\widetilde{e}}_{2k}\right) \,(A_{k+1}^{-1})^{(2,2)} \nonumber \\= & {} \mathbb {\widetilde{T}}_{2m}\,{\widetilde{e}}_{2k+1} \,A_{k+1}^{(1,1)}\,(A_{k+1}^{-1})^{(1,2)}\\&+\left( {\widetilde{e}}_{2k}-\left[ \begin{array}{c} \mathbb {\widetilde{T}}_{2k}\\ 0_{2(m-k)p \times 2kp}\\ \end{array}\right] \,\mathbb {H}_{2k}\,{\widetilde{e}}_{2k}\right) \,(A_{k+1}^{-1})^{(2,2)}. \end{aligned}$$

Then the proof is completed since we have $\mathbb {W}_{2m+2}^{T}\,A\,{\mathscr {V}}_{k+1}^{(2)}=\mathbb {\widetilde{T}}_{2m}\,{\widetilde{e}}_{2k+2}.$ $\square$

Now we show the same result for the matrix $\widetilde{\mathbb {L}}_{2m}$, and we derive recursions to compute the block columns of this matrix directly from the block columns of $\widetilde{ \mathbb {H}}_{2m}$ without using extra matrix-vector products with $A^{-T}$.

Proposition 4

Let $\widetilde{\mathbb {L}}_{2m}$ be the upper Hessenberg matrix $\widetilde{\mathbb {L}}_{2m}= \mathbb {W}_{2m+2}^{T}\, A^{-1}\,\mathbb {V}_{2m}$. Then, the following relations hold

$$\begin{aligned} \widetilde{\mathbb {L}}_{2m}\, {\widetilde{e}}_{1}=\left[ {\widetilde{e}}_{1} \,\varLambda _{V}^{(1,2)}+{\widetilde{e}}_{2} \,\varLambda _{V}^{(2,2)}\right] \,(\varLambda _{V}^{(1,1)})^{-1}, \end{aligned}$$

(28)

and for $k=1,\ldots ,m,$ we have

$$\begin{aligned} \widetilde{\mathbb {L}}_{2m}\,{\widetilde{e}}_{2k}= & {} \widetilde{\mathbb {H}}_{2m}\,{\widetilde{e}}_{2k}, \end{aligned}$$

(29)

$$\begin{aligned} \widetilde{\mathbb {L}}_{2m}\,{\widetilde{e}}_{2k+1}= & {} \left( {\widetilde{e}}_{2k-1}-\left[ \begin{array}{c} \widetilde{\mathbb {L}}_{2k}\\ 0_{2(m-k)p \times 2kp}\\ \end{array}\right] \mathbb {H}_{2k}\,{\widetilde{e}}_{2k-1}\right) \,(A_{k+1}^{(1,1)})^{-1}. \end{aligned}$$

(30)

Proof

To prove (28), we suppose that $\varLambda _{V}^{(1,1)}$ is nonsingular and use (26), then we obtain

$$\begin{aligned} A^{-1}\,{\mathscr {V}}_{1}^{(1)}=A^{-1}\,V\,(\varLambda _{V}^{(1,1)})^{-1}=[{\mathscr {V}}_{1}^{(1)}\,\varLambda _{V}^{(1,2)}+{\mathscr {V}}_{1}^{(2)} \,\varLambda _{V}^{(2,2)}]\,( \varLambda _{V}^{(1,1)})^{-1}. \end{aligned}$$

We pre-multiply the above equality by $\mathbb {W}_{2m+2}^{T}$ and we use the biorthogonality condition to get

$$\begin{aligned} \mathbb {W}_{2m+2}^{T} A^{-1}\,{\mathscr {V}}_{1}^{(1)}=\left[ {\widetilde{e}}_{1}\,\varLambda _{V}^{(1,2)}+{\widetilde{e}}_{2}\,\varLambda _{V}^{(2,2)}\right] \,(\varLambda _{V}^{(1,1)})^{-1}. \end{aligned}$$

Then, equation (28) is obtained by using the fact that $\mathbb {V}_{2m+2} A^{-1}\,{\mathscr {V}}_{1}^{(1)}=\widetilde{\mathbb {L}}_{2m}\,{\widetilde{e}}_{1}$.

For the other even matrices, we proceed as follows. We start by using (22) and (23) to have

$$\begin{aligned} A^{-1}\,{\mathscr {V}}_{k}^{(2)}= & {} U_{k+1}\, {\widetilde{e}}_{2}+\mathbb {V}_{2k}\,\mathbb {H}_{2k}\,{\widetilde{e}}_{2k}, \nonumber \\= & {} {\mathscr {V}}_{k+1}\,A_{k+1}\,{\widetilde{e}}_{2}+\mathbb {V}_{2k}\,\mathbb {H}_{2k}\,{\widetilde{e}}_{2k} \nonumber \\= & {} \mathbb {V}_{2k+2} \,\widetilde{\mathbb {H}}_{2k} \,{\widetilde{e}}_{2k}. \end{aligned}$$

Now, we multiply on the left by $\mathbb {W}_{2m+2}^{T}$ to get

$$\begin{aligned} \mathbb {W}_{2m+2}^{T}\,A^{-1}\,{\mathscr {V}}_{k}^{(2)}=\mathbb {W}_{2m+2}^{T}\,\mathbb {V}_{2k+2}\, \widetilde{\mathbb {H}}_{2k}\,{\widetilde{e}}_{2k}, \end{aligned}$$

hence

$$\begin{aligned} \mathbb {W}_{2m+2}^{T}\,A^{-1}\,{\mathscr {V}}_{k}^{(2)}=\left[ \begin{array}{c} I_{2(k+1)p}\\ 0_{2(m-k)p \times 2(k+1)p}\\ \end{array}\right] \,\widetilde{\mathbb {H}}_{2k}\,{\widetilde{e}}_{2k} \end{aligned}$$

therefore

$$\begin{aligned} \widetilde{\mathbb {L}}_{2m}\,{\widetilde{e}}_{2k}=\left[ \begin{array}{c} \widetilde{\mathbb {H}}_{2k}\\ 0_{2(m-k)p \times 2kp}\\ \end{array}\right] =\widetilde{\mathbb {H}}_{2m}\,{\widetilde{e}}_{2k}, \end{aligned}$$

which gives relation (29).

For the odd matrices, we multiply (22) on the left by $A^{-1}$ and we consider only the first p columns of each block to obtain

$$\begin{aligned} A^{-1}\,U_{k+1}{\widetilde{e}}_{1}={\mathscr {V}}_{k}^{(1)}-A^{-1}\,\mathbb {V}_{2k}\,\mathbb {H}_{2k}\,{\widetilde{e}}_{2k-1}. \end{aligned}$$

Since $U_{k+1}={\mathscr {V}}_{k+1}\,A_{k+1}$, we have

$$\begin{aligned} U_{k+1}{\widetilde{e}}_{1}={\mathscr {V}}_{k+1}^{(1)}A_{k+1}^{(1,1)}, \end{aligned}$$

and if $A_{k+1}^{(1,1)}$ is nonsingular, we obtain

$$\begin{aligned} A^{-1}\,{\mathscr {V}}_{k+1}^{(1)}=A^{-1}\,U_{k+1}{\widetilde{e}}_{1}\,(A_{k+1}^{(1,1)})^{-1}=({\mathscr {V}}_{k}^{(1)}-A^{-1}\,\mathbb {V}_{2k}\,\mathbb {H}_{2k}\,{\widetilde{e}}_{2k-1})\,(A_{k+1}^{(1,1)})^{-1}. \end{aligned}$$

Multiplying from the left by $\mathbb {W}_{2m+2}^{T}$, we get

$$\begin{aligned} \mathbb {W}_{2m+2}^{T}\,A^{-1}\,{\mathscr {V}}_{k+1}^{(1)}=(\mathbb {W}_{2m+2}^{T}\,{\mathscr {V}}_{k}^{(1)}-\mathbb {W}_{2m+2}^{T}\,A^{-1}\mathbb {V}_{2k}\,\mathbb {H}_{2k}\,{\widetilde{e}}_{2k-1})\,(A_{k+1}^{(1,1)})^{-1}, \end{aligned}$$

and then

$$\begin{aligned} \widetilde{\mathbb {L}}_{2m}\,{\widetilde{e}}_{2k+1}= & {} \left( \mathbb {W}_{2m+2}^{T}\, \mathbb {V}_{2m+2}\,{\widetilde{e}}_{2k-1}-\mathbb {W}_{2m+2}^{T}\,A^{-1}\,\mathbb {V}_{2m}\right. \\&\quad \left. \left[ \begin{array}{c} I_{2kp}\\ 0_{2(m-k)p \times 2kp}\\ \end{array}\right] \, \mathbb {H}_{2k}\,{\widetilde{e}}_{2k-1}\right) \,(A_{k+1}^{(1,1)})^{-1} \nonumber \\= & {} \left( {\widetilde{e}}_{2k-1}-\widetilde{\mathbb {L}}_{2m}\,\left[ \begin{array}{c} I_{2kp}\\ 0_{2(m-k)p \times 2kp}\\ \end{array}\right] \, \mathbb {H}_{2k}\,{\widetilde{e}}_{2k-1}\right) \,(A_{k+1}^{(1,1)})^{-1} \nonumber \\= & {} \left( {\widetilde{e}}_{2k-1}-\left[ \begin{array}{c} \widetilde{\mathbb {L}}_{2k}\\ 0_{2(m-k)p \times 2kp}\\ \end{array}\right] \, \mathbb {H}_{2k}\,{\widetilde{e}}_{2k-1}\right) \,(A_{k+1}^{(1,1)})^{-1}, \end{aligned}$$

which gives the relation (30). $\square$

The results of the next two propositions will be used to prove other properties in the next section which is devoted to the application of the extended block Lanczos method to obtain reduced order models in large scale dynamical systems. As we will see, the method allows one to approximate low and high frequencies of the corresponding transfer function at the same time.

Proposition 5

Let $\mathbb {V}_{2m}$ and $\mathbb {W}_{2m}$ be the matrices generated by Algorithm 2, and let $\mathbb {L}_{2m}=\mathbb {W}_{2m}^{T}\,A^{-1}\,\mathbb {V}_{2m}$. Then we have

$$\begin{aligned} A^{-j}\,\mathbb {V}_{2m}\,\mathbb {E}_{1}= & {} \mathbb {V}_{2m}\,\mathbb {L}_{2m}^{j}\,\mathbb {E}_{1}, \ \ \ \ \ \text{ for } \ j=0,\ldots ,m-1, \end{aligned}$$

(31)

$$\begin{aligned} (A^{-T})^{j}\,\mathbb {W}_{2m}\,\mathbb {E}_{1}= & {} \mathbb {W}_{2m}\,(\mathbb {L}_{2m}^{T})^{j}\,\mathbb {E}_{1}, \ \ \ \ \ \text{ for } \ j=0,\ldots ,m-1. \end{aligned}$$

(32)

Moreover, we have

$$\begin{aligned} \mathbb {T}_{2m}^{-1} \,\mathbb {E}_{j}=\mathbb {L}_{2m} \, \mathbb {E}_{j}, \ \ \ \ \text{ for } \ j=1,\ldots ,m-1, \end{aligned}$$

(33)

where $\mathbb {E}_{j}$ is an $2mp \times 2p$ tall and skinny matrix with an identity matrix of dimension p at the $j^{th}$ block and zero elsewhere.

Proof

Using equation (19) of Proposition 2, we have

$$\begin{aligned} A^{-1} \mathbb {V}_{2m} = \mathbb {V}_{2m} \mathbb {L}_{2m}+{\mathscr {V}}_{m+1}L_{m+1,m}\mathbb {E}_{m}^{T}, \end{aligned}$$

(34)

we pre-multiply j times by $A^{-1}$, we re-arrange the result and then we multiply from the right by $\mathbb {E}_{1}$ to get

$$\begin{aligned} A^{-j} \, \mathbb {V}_{2m} \, \mathbb {E}_{1}= \mathbb {V}_{2m} \, \mathbb {L}_{2m}^{j}\,\mathbb {E}_{1}+\sum _{i=1}^{j} A^{-(i-1)}\,{\mathscr {V}}_{m+1}\,L_{m+1,m}\,\mathbb {E}_{m}^{T}\mathbb {L}_{2m}^{j-i}\,\mathbb {E}_{1}. \end{aligned}$$

As $\mathbb {L}_{2m}$ is an upper block Hessenberg matrix, it follows that $\mathbb {E}_{m}^{T}\,\mathbb {L}_{2m}^{j-i}\,\mathbb {E}_{1}=0$, for $j=1,\ldots ,m-1$, and then Eq. (31) is verified. In a similar way, we can use equation (21) of Proposition 2 to show (32).

Now to prove (33), we multiply (34) from the right by $\mathbb {E}_{j}$ to get

$$\begin{aligned} A^{-1}\,\mathbb {V}_{2m}\,\mathbb {E}_{j} = \mathbb {V}_{2m} \,\mathbb {L}_{2m}\,\mathbb {E}_{j},\quad \ \text{ for } \ j=1,\ldots ,m-1. \end{aligned}$$

We multiply the above equality by $\mathbb {W}_{2m}^{T}\,A$ from the left and we use the biorthogonality condition to have

$$\begin{aligned} \mathbb {E}_{j}=\mathbb {T}_{2m}\,\mathbb {L}_{2m} \,\mathbb {E}_{j}, \quad \ \text{ for } \ j=1,\ldots ,m-1. \end{aligned}$$

Finally, Eq. (33) can be obtained if we assume that $\mathbb {T}_{2m}$ is nonsingular. $\square$

The following result is proven in [1], it gives a general property for two upper Hessenberg matrices.

Proposition 6

Let $T=(T_{i,j})$ and $L=(L_{i,j})$ be two upper Hessenberg matrices with blocks $T_{i,j},~L_{i,j} \in \mathbb {R}^{p \times p}$ for $i,j=1,\ldots ,m$, and suppose that

$$\begin{aligned} T\,\mathbb {E}_{j}= L\,\mathbb {E}_{j}, \ \ \ \ \text{ for } \ j=1,\ldots ,m-1. \end{aligned}$$

Then

$$\begin{aligned} T^{k}\,\mathbb {E}_{1}= L^{k}\,\mathbb {E}_{1}, \ \ \ \ \text{ for } \ k=1,\ldots ,m-1, \end{aligned}$$

where $\mathbb {E}_{j}$ is an $2mp \times 2p$ tall and skinny matrix with an identity matrix of dimension p at the $j^{th}$ block and zero elsewhere.

3 Application to model reduction problems

The aim of this section is to show how to use the extended block Lanczos algorithm described in last section to reduce the order of the original dynamical system described by (1).

A classical way for relating the input to the output is to use the transfer function of the original system (1). If we apply the Laplace transform to (1), we obtain

$$\begin{aligned} \left\{ \begin{array}{l c l} s\,X(s) &{} = &{} A\,X(s)+B\,U(s)\\ Y(s) &{} = &{} C\,X(s),\\ \end{array} \right. \end{aligned}$$

where X(s),  Y(s) and U(s) are the Laplace transforms of x(t),  y(t) and u(t), respectively. If we eliminate X(s) in the previous two equations we obtain $Y(s)=F(s)\,U(s)$, where F(s) is called the transfer function of the system (1) and defined as

$$\begin{aligned} F(s)=C\,(s\,I_{n}-A)^{-1}\,B. \end{aligned}$$

When $p=1$, the dynamical system is called Single-Input Single-Output (SISO) system. When the dimension n is very large, the simulation and control of the dynamical system can lead to a huge computational burden. Then, the model reduction technique is to replace (1) by a lower-order r-dimensional dynamical system having the following form

$$\begin{aligned} \left\{ \begin{array}{lll} \dot{x}_{r}(t) = A_{r}\,x_{r}(t)+B_{r}\,u(t)\\ y_{r}(t) = C_{r}\,x_{r} (t),\\ \end{array} \right. \end{aligned}$$

(35)

where $A_{r} \in \mathbb {R}^{r \times r},~B_{r},~C_{r}^{T} \in \mathbb {R}^{r \times p}$ and $r \ll n$. We require the approximate model (35) to preserve properties of the original system (1) like regularity, stability and passivity [30]. The output $y_{r}$ should be close to the output y of the original system which means that the error should be small for an appropriate norm. The associated low-order transfer function is denoted by

$$\begin{aligned} F_{r}(s)=C_{r}(s\,I_{r}-A_{r})^{-1}\,B_{r}. \end{aligned}$$

Various model reduction methods for MIMO systems have been explored during the last years. Some of them are based on Krylov subspace methods (moment matching) while others use balanced truncation; see [3, 15, 18] and the references therein. A popular model reduction technique for large scale systems is the moment matching method considered first in [14]. The aim of this approach is to project the original system onto Krylov subspaces computed by Arnoldi or Lanczos processes for SISO and MIMO systems; see [9, 12, 20, 21, 23] and the references therein. Unfortunately, the standard version of these methods tend to create reduced order models that poorly approximate low frequency dynamics.

To overcome this problem, we present a new projection method that allows us to compute a low order reduced model (35) by using the extended block Lanczos process. The application of this algorithm to the pairs (A, B) and $(A^{T},C^{T})$ gives two biorthogonal bases $\mathbb {V}_{2m}$ and $\mathbb {W}_{2m}$. Then the reduced order model (35) will be defined by setting $r=2m$ and

$$\begin{aligned} A_{2m}=\mathbb {T}_{2m}=\mathbb {W}_{2m}^{T}\,A \mathbb {V}_{2m}, \; \; \; B_{2m}=\mathbb {W}_{2m}^{T}\,B \; \; \; \text{ and } \; \; \; C_{2m}=C \mathbb {V}_{2m}. \end{aligned}$$

The approach used here is the moment matching approximations, see [5, 6, 16, 17] and the references therein. The aim of this technique is to produce a reduced order model such that k moments are to be matched, where k is appropriately chosen.

Now, we use the Laurent series of the transfer function F around $\sigma =\infty$ to get

$$\begin{aligned} F(s)= \displaystyle \sum _{i=0}^{\infty } f_i\,s^{-i}, \end{aligned}$$

where $f_{i}=C\,A^{i}\,B$ for $i \ge 0$, are called the Markov parameters. Similarly, expanding the reduced transfer function $F_{2m}$ around infinity gives the matrix coefficients $\tilde{f}_{i}=C_{2m}\,\mathbb {T}_{2m}^{i} \,B_{2m}$, for $i \ge 0$. If $\sigma =0$, the Laurent series of F around $\sigma$ can be written as

$$\begin{aligned} F(s)= \sum _{i=0}^{\infty } m_{i+1}\,s^{i}, \end{aligned}$$

where the matrix coefficients are $m_{j}=-C\,A^{-j}\,B, \ \ for \ j \ge 1$.

The development of the reduced transfer function $F_{2m}$ around zero gives the matrix coefficient $\tilde{m}_{i}=-C_{2m}\,\mathbb {T}_{2m}^{-i}\,B_{2m}, \ for \ i \ge 1$.

Then, the aim of the moment matching problem using the extended block Lanczos algorithm is to produce a reduced order model such that the first $2m-1$ Markov parameters and moments are to be matched, i.e.,

$$\begin{aligned} \tilde{f}_{j}=f_{j}, \ \ \ \text{ for } \ j=0,\ldots ,2m-2, \end{aligned}$$

(36)

and

$$\begin{aligned} \tilde{m}_{j}=m_{j}, \ \ \ \text{ for } \ j=0,\ldots ,2m-2. \end{aligned}$$

(37)

For the Markov parameters, the equality (36) is already proven in the literature, see [20] and the references therein. The following result shows that the first $2m-1$ moments resulting from the Laurent expansion of the transfer function F around $\sigma =0$ are also matched.

Proposition 7

Let $\tilde{m}_{j}$ and $m_j$ be the matrix moments given by the Laurent expansions of the transfer functions $F_{2m}$ and F, respectively, around $\sigma =0$. Then, the first $2m-1$ moments of the original and the reduced models are the same, that is,

$$\begin{aligned}\widetilde{m}_{j}=m_{j}, \ \text{ for } \ j=0,\ldots ,2(m-1).\end{aligned}$$

Proof

Let $j \in \lbrace 0,1,\ldots ,2(m-1) \rbrace$ and $j_1, j_{2} \in \lbrace 0,1,\ldots ,m-1 \rbrace$ such that $j_1+j_2=j$. Then, we have

$$\begin{aligned} m_{j} = C\,A^{-j}\,B = C\,A^{-(j_{1}+j_{2})}\,B=C\,A^{-j_{1}}\,A^{-j_{2}}\,B. \end{aligned}$$

(38)

Applying Algorithm 1 to B and C gives

$$\begin{aligned} B = {\mathscr {V}}_{1}\,\left[ \begin{array}{c} \varLambda _{V}^{(1,1)}\\ 0\\ \end{array}\right] \ \ \quad \text{ and } \quad \ \ C=\left[ \begin{array}{c} \varLambda _{W}^{(1,1)}\\ 0\\ \end{array}\right] ^{T}\,{\mathscr {W}}_{1}^{T}. \end{aligned}$$

Substituting this result in Eq. (38) yields

$$\begin{aligned} m_{j}= & {} \left[ \begin{array}{c} \varLambda _{W}^{(1,1)}\\ 0\\ \end{array}\right] ^{T}\,{\mathscr {W}}_{1}^{T}\,A^{-j_{1}}\,A^{-j_{2}}\,{\mathscr {V}}_{1} \left[ \begin{array}{c} \varLambda _{V}^{(1,1)}\\ 0\\ \end{array}\right] \nonumber \\= & {} \left[ \begin{array}{c} \varLambda _{W}^{(1,1)}\\ 0\\ \end{array}\right] ^{T}\,\mathbb {E}_{1}^{T}\,\mathbb {W}_{2m}^{T}\,A^{-j_{1}}\,A^{-j_{2}}\, \mathbb {V}_{2m}\,\mathbb {E}_{1}\,\left[ \begin{array}{c} \varLambda _{V}^{(1,1)}\\ 0\\ \end{array}\right] . \end{aligned}$$

Therefore, using the result of Proposition 5, we get

$$\begin{aligned} m_{j}= & {} \left[ \begin{array}{c} \varLambda _{W}^{(1,1)}\\ 0\\ \end{array}\right] ^{T}\,\mathbb {E}_{1}^{T}\,\mathbb {L}_{2m}^{j_{1}}\,\mathbb {W}_{2m}^{T}\,\mathbb {V}_{2m}\,\mathbb {L}_{2m}^{j_{2}}\,\mathbb {E}_{1}\,\left[ \begin{array}{c} \varLambda _{V}^{(1,1)}\\ 0\\ \end{array}\right] \nonumber \\= & {} \left[ \begin{array}{c} \varLambda _{W}^{(1,1)}\\ 0\\ \end{array}\right] ^{T}\, \mathbb {E}_{1}^{T}\, \mathbb {L}_{2m}^{j} \, \mathbb {E}_{1} \,\left[ \begin{array}{c} \varLambda _{V}^{(1,1)}\\ 0\\ \end{array}\right] . \end{aligned}$$

On the other hand, since $\mathbb {L}_{2m}$ and $\mathbb {T}^{-1}_{2m}$ are both Hessenberg matrices that verify $\mathbb {T}^{-1}_{2m}\,\mathbb {E}_{j}=\mathbb {L}_{2m} \mathbb {E}_{j}$, then the application of Proposition 6 gives

$$\begin{aligned} \mathbb {L}_{2m}^{j}\,\mathbb {E}_{1}=\mathbb {T}_{2m}^{-j}\,\mathbb {E}_{1}, \ \ \ \ \text{ for } \ j=0,\ldots ,m-1, \end{aligned}$$

and so

$$\begin{aligned} m_{j} = \left[ \begin{array}{c} \varLambda _{W}^{(1,1)}\\ 0\\ \end{array}\right] ^{T}\,\mathbb {E}_{1}^{T}\,\mathbb {T}_{2m}^{-j}\,\mathbb {E}_{1}\, \left[ \begin{array}{c} \varLambda _{V}^{(1,1)}\\ 0\\ \end{array}\right]= & {} \left[ \begin{array}{c} \varLambda _{W}^{(1,1)}\\ 0\\ \end{array}\right] ^{T}\,{\mathscr {W}}_{1}^{T}\,\mathbb {V}_{2m}\,\mathbb {T}_{2m}^{-j}\,\mathbb {W}_{2m}^{T} {\mathscr {V}}_{1}\,\left[ \begin{array}{c} \varLambda _{V}^{(1,1)}\\ 0\\ \end{array}\right] \nonumber \\= & {} C\,\mathbb {V}_{2m}\,\mathbb {T}_{2m}^{-j}\,\mathbb {W}_{2m}^{T}B \nonumber \\= & {} C _{2m}\,\mathbb {T}_{2m}^{-j}\,B_{2m} \nonumber \\= & {} \widetilde{m}_{j}, \end{aligned}$$

which completes the proof of Proposition 7. $\square$

4 Numerical experiments

In this section, we give some experimental results to show the effectiveness of the extended block Lanczos algorithm (EBLA) when applied to model reduction in large scale dynamical systems. All the experiments were performed on a computer with an Intel Core i5 processor at 1.3GHz and 8GB of RAM. The algorithms were coded in Matlab 8.0.

To compute the $\mathscr {H}_{\infty }$-norm $\Vert F-F_{2m} \Vert _{\infty }=\sup _{\omega \in \mathbb {R}} \Vert F(j \omega )-F_{2m}(j \omega ) \Vert _{2}$, where $\omega \in [10^{-6},10^{6}]$ and $j=\sqrt{-1}$, the following functions from LYAPACK [27] were used :

• lp_lgfrq: Generates the set of logarithmically distributed frequency sampling points.

• lp_gnorm: Computes $\Vert F(j \omega )-F_{2m}(j \omega ) \Vert _{2}$.

In our experiments, we used some matrices from LYAPACK and different known benchmark models listed in Table 1.

Table 1 The test models

Example 1. The first test model is the International Space Station (ISS) model from [24]. Its dimension is $n = 270$ with 3 inputs and 3 outputs. This is a small dimension model but it is generally difficult and always considered as a benchmark test. For the second experiment, we considered the Flow Meter model. This system is obtained from the discretization of a 2D convective thermal flow problem (flow meter model v0.5) from the Oberwolfach model reduction benchmark collection¹, with 5 inputs and 5 outputs.

The left curves of Fig. 1 (ISS) and Fig.  2 (Flow Meter) show the frequency responses of the original system (circles) compared with the frequency responses of its approximations (solid line) for $m=5$ . The right curves of these figures represent the exact error norm $\Vert F(j\,\omega )- F_{2m}(j\,\omega ) \Vert _{2}$ for different frequencies $\omega \in [10^{-6},~10^6]$.

Fig. 1

Left: $\Vert {F(j \omega )} \Vert _{2}$ (circles) and its approximations $\Vert F_{2m}(j \omega ) \Vert _{2}$ (solid). Right: the error norm $\Vert F(j \omega )- F_{2m}(j \omega ) \Vert _{2}$ for the ISS model

Fig. 2

Results for the flow-meter model. Left: $\Vert {F(j\,\omega )} \Vert _{2}$(circles) and its approximations $\Vert F_{2m}(j\, \omega ) \Vert _{2}$ (solid). Right: the error norm $\Vert F(j\, \omega )- F_{2m}(j\,\omega ) \Vert _{2}$

From Figs. 1 and 2, it is clear that the extended block Lanczos algorithm gives good results for low and hight frequencies, i.e., the moments and Markov parameters of the original transfer function are well approximated by those of the reduced transfer function at the same time.

Example 2. In this example, we plotted the $\mathscr {H}_{\infty }$ error norm $\Vert F-F_{2m} \Vert _{\infty }$ versus the number m of iterations for two different models. The first one is the modified FOM model from [24]. We notice that originally, the FOM model is a SISO system and we modified the inputs and outputs to get a MIMO system. The matrices B and C are then given by

$$\begin{aligned} B=[b_{1},\ldots ,b_{6}],~~C^{T}=[c_{1},\ldots ,c_{6}], \end{aligned}$$

where $b_{1}^{T}=c_{1}=(\underbrace{10,\ldots ,10}_{6}, \underbrace{1,\ldots ,1}_{1000})$ and $b_{2},\ldots ,b_{6};~~c_{2},\ldots ,c_{6}$ are random column vectors.

For the second experiment, we used the fdm model [27]. For this model, the corresponding matrix A is obtained from the centered finite difference discretization of the operator

$$\begin{aligned} L_{A}(u) = \varDelta u-f(x,y) \frac{\partial u}{\partial x}-g(x,y) \frac{\partial u}{\partial y}-h(x,y)u, \end{aligned}$$

on the unit square $[0, 1] \times [0, 1]$ with homogeneous Dirichlet boundary conditions with

$$\begin{aligned} f(x,y) = e^{xy}, \; g(x,y) = sin(xy)\; \ \ and \ \ \;h(x,y) = y^{2}-x^{2}. \end{aligned}$$

The matrices B and C were random matrices with entries uniformly distributed in [0, 1]. The number of inner grid points in each direction was $n_0=100$ and the dimension of A is $n = n_0^2=10^4$. For this experiment, we used $p=6$. As can be shown from Fig. 3, the extended block Lanczos algorithm (EBLA) gives good results with small values of m.

Fig. 3

The $\mathscr {H}_{\infty }$ error $\Vert F- F_{2m} \Vert _{\infty }$ versus the number of iterations for the fdm model (left curve) and the modified fom model (right curve)

Example 3. In the last example we compared the extended block Lanczos algorithm (EBLA) with the Iterative Rational Krylov Algorithm IRKA proposed in [7, 19] . We used four models: the ISS, the add32, the Modified fom and the fdm model (with $n=10^4$, $p=6$). In Table 2, we listed the obtained $\mathscr {H}_{\infty }$ norm of the error $\Vert F-F_{2m} \Vert _{\infty }$, the required cpu-time and the dimension of the projected subspace. A maximum number of $m_{max}= 100$ iterations was allowed to the IRKA method. As observed from Table 2, IRKA and EBLA return similar results for the $\mathscr {H}_{\infty }$ norm, with an important advantage in cpu-time for the EBLA.

Table 2 Comparison between IRKA and EBLA for ISS, Modified fom and fdm models

5 Conclusion

In the present paper, we proposed a new process called extended block Lanczos, allowing us to build biorthogonal bases of two extended block Krylov subspaces associated to the matrices A, $A^T$ and their inverses. We derived some theoretical results such as algebraic relations satisfied by the matrices obtained by this process. We showed how the extended block Lanczos algorithm could be applied to model order reductions for Multiple-Input Multiple-Output first-order linear dynamical systems. The proposed procedure is tested on some benchmark problems of medium and large dimensions, and the numerical results show that the extended block Lanczos algorithm allows one to obtain reduced order models of small dimensions that approximate well the initial large models.