1 Introduction

We consider the following multi-input and multi-output (MIMO) linear time invariant (LTI) dynamical system

$$\begin{aligned} \left\{ \begin{array}{lll} \dot{x}(t) &{} = &{} Ax(t)+Bu(t),\\ y(t) &{} = &{} Cx(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 system matrices \(B, C^{T} \in {\mathbb {R}}^{n \times p}\) and \(A \in {\mathbb {R}}^{n \times n}\) are assumed to be large and sparse. The transfer function of the original system (1) is defined by

$$\begin{aligned} H(s)=C(sI_{n}-A)^{-1}B. \end{aligned}$$

Then, the aim of the model-order reduction problem is to produce a low-order dimensional system that preserves the important properties of the original system and has the following form

$$\begin{aligned} \left\{ \begin{array}{l} \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}$$
(2)

where \(A_r \in {\mathbb {R}}^{r \times r}, B_r, C_r^{T} \in {\mathbb {R}}^{r \times p}\) and \(r \ll n\). The associated low-order transfer function is denoted by

$$\begin{aligned} H_r(s)=C_r(s{I_{r}}-A_r)^{-1}B_r. \end{aligned}$$

Various model reduction methods for MIMO systems have been explored these last years. Some of them are based on Krylov subspace methods (moment matching) while others use balanced truncation; see [3, 17, 21] and the references therein. In particular, the Lanczos process has been used for the single-input and single-output (SISO) (the case \(p=1\)) and MIMO dynamical systems; see [12, 13, 23, 24] and the references therein. The standard version of the Lanczos algorithm builds reduced order models that poorly approximate some frequency dynamics and to overcome this problem, rational Krylov subspace methods have been developed these last years [11, 14, 15, 19, 20, 29, 31]. However, the selection of the interpolation points is a major problem of these methods and they have to be appropriately chosen to get good approximations. When \(p >1\), we can use Krylov subspace methods based on block versions of the Arnoldi or the Lanczos algorithms. In this paper, we are interested in multi-point rational interpolation method for model order reduction for MIMO systems, which was first proposed by Yousuff and Skelton in [32]. By multipoint rational interpolation we mean that the reduced system matches the moments of the original system at multiple interpolation points. One of the main problems is the selection of suitable shifts to guarantee a good convergence of the process. Various methods have been proposed in the literature to construct the set of interpolation points. In [7, 22] Gugercin et al. proposed an Iterative Rational Krylov Algorithm (IRKA) to compute a reduced order model satisfying the first-order conditions for the \({{\mathscr {H}}}_{2}\) approximation. Other adaptive methods (for the SISO case) are introduced in [9, 19, 20, 25, 27, 30] and the references therein.

The paper is organized as follows. In Sect. 2, we first review some moment matching techniques for model order reduction. In Sect. 3, we propose a rational block Lanczos-type process and give some algebraic properties. An error expression between the original and the reduced-order transfer functions is derived in Sect. 4. In Sect. 5 we propose adaptive techniques for selecting some interpolation points. The last section is devoted to some numerical experiments.

2 Moment Matching Problems

Let \(H(s)=C(sI_{n}-A)^{-1}B\) be the transfer function of the linear dynamical system as described in the state space form (1). If H(s) is expanded as a power series around a given finite point \(\sigma _{0} \in {\mathbb {R}}\), then we get

$$\begin{aligned} H(s)=h_{0}+h_{1}(s-\sigma _{0})+h_{2}(s-\sigma _{0})^{2}+... \end{aligned}$$

where the coefficients \(h_{j}, j \ge 0\) are known as the moments of the dynamical system around \(\sigma _{0}\) and they are given by

$$\begin{aligned} h_{j}(\sigma _{0})=C(\sigma _{0}I_{n}-A)^{-(j+1)}B. \end{aligned}$$

These moments are the values of the transfer function of the system (1) and its derivatives evaluated at \(\sigma _{0}\) (they are also called the shifted moments). The model-order reduction problem using a moment matching method consists in finding a lower order transfer function \(H_r(s)\) having a power series expansion at \(\sigma _{0}\) as

$$\begin{aligned} H_r(s)=\hat{h}_{0}+\hat{h}_{1}(s-\sigma _{0})+\hat{h}_{2}(s-\sigma _{0})^{2}+... \end{aligned}$$

such that the first k moments are matched, i.e.,

$$\begin{aligned} h_{j}(\sigma _{0})=\hat{h}_{j}(\sigma _{0}), \ j=0,...,k-1, \end{aligned}$$

for an appropriate \(k \ll n\). The reduced-order model resulting is known as a rational interpolation [1]. If \(\sigma _{0}=0\), the moments satisfy \(h_{j}=-CA^{-(j{+1})}B\) for \(j \ge 0\) and the problem is known as a Padé approximation [6]. The Laurent series of the transfer function H around \(\sigma _0=\infty \) is expressed as .

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

where \(h_{i}=CA^{i}B\) for \(i \ge 0\) are called the Markov parameters and the corresponding problem is known as a partial realization [18]. We can also consider multiple interpolation points, the resulting reduced-order model is a multipoint Padé approximation or a multipoint rational interpolation [26].

2.1 The Standard Block Lanczos Algorithm

Let V and W be two initial blocks of \({\mathbb {R}}^{n \times p}\), and consider the following block Krylov subspaces

$$\begin{aligned} \mathscr {K}_{m}(A,V)= & {} \mathrm{Range} \left( V,AV,\ldots , A^{m-1}V\right) \; \mathrm{and} \; \mathscr {K}_{m}(A^T,W)\\= & {} \mathrm{Range} \left( W,\ldots , ({A^T})^{(m-1)}W\right) . \end{aligned}$$

The nonsymmetric block Lanczos algorithm applied to the pairs (A, V) and \((A^{T},W)\) generates two sequences of bi-orthonormal \(n\times p\) matrices \(\lbrace V_{i} \rbrace \) and \(\lbrace W_{j} \rbrace \) such that

$$\begin{aligned} \mathscr {K}_{m}(A,V)=\mathrm{Range} ( V_{1},V_{2},\ldots ,V_{m} ). \end{aligned}$$

and

$$\begin{aligned} \mathscr {K}_{m}(A^{T},W)=\mathrm{Range} ( W_{1},W_{2},\ldots ,W_{m} ). \end{aligned}$$

The matrices \(V_i\) and \(W_j\) that are generated by the block Lanczos algorithm satisfy the biorthogonality conditions, i.e.

$$\begin{aligned} \left\{ \begin{array}{c c c} W_{j}^{T} V_{i}=0_{p}, \quad \textit{if} \ i \ne j,\\ W_{j}^{T} V_{i}=I_{p}, \quad \textit{if} \ i = j.\\ \end{array} \right. \end{aligned}$$
(3)

Next, we give a stable version of the nonsymmetric block Lanczos algorithm that was defined in [4]. The algorithm is summarized as follows.

figure a

Setting \({\mathbb {V}}_{m}=[V_{1},V_{2},\ldots ,V_{m} ]\) and \({\mathbb {W}}_{m}=[ W_{1},W_{2},\ldots ,W_{m} ]\), we have the following block Lanczos relations

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

and

$$\begin{aligned} A^{T}{\mathbb {W}}_{m}={\mathbb {W}}_{m}T_{m}^{T}+W_{m+1} \delta _{m+1}^{T}E_{m}^{T}, \end{aligned}$$

where \(E_m\) is last \(mp\times p\) block of the identity matrix \(I_{mp}\) and \(T_m\) is the \(mp \times mp\) block tridiagonal matrix defined by

$$\begin{aligned} T_{m}=\left( \begin{array}{cccccc} \alpha _{1} &{} \delta _{2}&{} &{} &{} \\ \beta _{2} &{} \alpha _{2} &{} . &{} &{} \\ &{} .&{} . &{} .&{} \\ &{} &{} .&{} . &{} \delta _{m} \\ &{} &{} &{} \beta _{m}&{} \alpha _{m} \end{array} \right) . \end{aligned}$$

Let \({\mathbb {V}}_{m}, {\mathbb {W}}_{m} \in {\mathbb {R}}^{n \times mp}\) be the bi-orthonormal matrices computed by Algorithm 1, the application of the oblique projector \(\Pi _m ={\mathbb {V}}_{m}{\mathbb {W}}_{m}^{T}\) on the original system (1) yields a reduced order system such that

$$\begin{aligned} A_m={\mathbb {W}}_{m}^{T}A{\mathbb {V}}_{m}, \ B_m={\mathbb {W}}_{m}^{T}B \ \mathrm{and} \ C_m=C {\mathbb {V}}_{m}. \end{aligned}$$
(4)

3 The Rational Block Lanczos Algorithm

Rational block Lanczos procedure [26] is an algorithm for constructing bi-orthonormal bases of the union of block Krylov subspaces. The following theorem is presented in [19] for SISO systems, and is extended to the MIMO case in [16]. It shows how we can construct the biorthogonal bases \(\{ V_{1},V_{2},\ldots ,V_{m}\}\) and \(\{ W_{1},W_{2},\ldots ,W_{m}\}\) of the rational Krylov subspaces \(\mathrm{Range} ( (A-\sigma _{1}I_n)^{-1}B, \ldots ,(A-\sigma _{m}I_n)^{-1}B )\) and \( \mathrm{Range} ( (A-\sigma _{1}I_n)^{-T}C^{T}, \ldots ,(A-\sigma _{m}I_n)^{-T}C^{T} ) \), respectively so that the multi-point rational interpolation problem is solved, i.e., the reduced order model has to interpolate the original transfer function H(s) and its first derivative at the interpolation points \(\lbrace \sigma _{i} \rbrace _{i=1}^{m}\).

Theorem 1

Given \(H(s)=C(sI_{n}-A)^{-1}B\) and m interpolation points \(\lbrace \sigma _{i} \rbrace _{i=1}^{m}\) that verify \(\sigma _{i} \ne \sigma _{j}\) for \(i \ne j\). Let \({\mathbb {V}}_{m} \in {\mathbb {R}}^{n \times mp}\) and \({\mathbb {W}}_{m} \in {\mathbb {R}}^{n \times mp}\) be obtained as follows:

$$\begin{aligned} \mathrm{Range} ({\mathbb {V}}_{m})= & {} \mathrm{Range} \left\{ (A-\sigma _{1}I_n)^{-1}B, \ldots ,(A-\sigma _{m}I_n)^{-1}B \right\} \nonumber \\ \mathrm{Range} ({\mathbb {W}}_{m})= & {} \mathrm{Range} \left\{ (A-\sigma _{1}I_n)^{-T}C^{T}, \ldots ,(A-\sigma _{m}I_n)^{-T}C^{T} \right\} \end{aligned}$$
(5)

with \({\mathbb {W}}_{m}^{T}{\mathbb {V}}_{m}=I_{mp}\). Then, the reduced order transfer function \(H_m(s)=C_m(sI_{mp}-A_m)^{-1}B_m\) obtained in (4) interpolates H(s) and its first derivative at \(\lbrace \sigma _{i} \rbrace _{i=1}^{m}\).

The rational block Lanczos-type algorithm is defined as follows

figure b

We notice that in our setting, we assume that we are not given the sequence of shifts \(\sigma _1, \sigma _2, \ldots , \sigma _{m+1}\) and then we need to include the procedure to automatically generate this sequence during the iterations of the process. This adaptive procedure well be defined in the next sections.

The rational block Krylov subspaces used in the above algorithm can be defined as

$$\begin{aligned} \mathscr {K}_{m}(A,B,\Sigma _m)= & {} \mathrm{Range} \left\{ (A-\sigma _{1}I_n)^{-1}B, \ldots ,\prod _{k=1}^m (A-\sigma _{k}I_n)^{-1}B \right\} , \end{aligned}$$
(6)
$$\begin{aligned} \mathscr {K}_{m}(A^{T},C^{T},\Sigma _m)= & {} \mathrm{Range} \left\{ (A-\sigma _{1}I_n)^{-T}C^{T},\ldots ,\prod _{k=1}^m(A-\sigma _{k}I_n)^{-T}C^{T} \right\} , \end{aligned}$$
(7)

where \(\Sigma _m=\{\sigma _{1},\ldots ,\sigma _{m}\}\) is the set of interpolation points.

Remark 1

A higher order multipoint moment matching is a simple generalization of Algorithm 2. In this case, \(2m_{i}\) moments are to be matched per interpolation point \(\sigma _{i}, i=1,\ldots ,l\), i.e.,

$$\begin{aligned} h_{j}(\sigma _{i})=\hat{h}_{j}(\sigma _{i}), \ j=0,\ldots ,2m_{i}-1, \ i=1,\ldots ,l, \end{aligned}$$
(8)

and the column vectors of the matrices \({\mathbb {V}}_{m}\) and \({\mathbb {W}}_{m}\) are determined from the l block Krylov subspaces \(\mathscr {K}_{m_{i}}(A,B,\sigma _{i})\) and \(\mathscr {K}_{m_{i}}(A^{T},C^{T},\sigma _{i})\), respectively, where

$$\begin{aligned} \mathscr {K}_{m_{i}}(A,B,\sigma _{i})=\mathrm{Range} \lbrace (A-\sigma _{i} I_{n})^{-1}B, (A-\sigma _{i} I_{n})^{-2}B,\ldots , (A-\sigma _{i} I_{n})^{-m}B \rbrace , \end{aligned}$$

see [12, 13]. The matrices \({\mathbb {V}}_{m}\) and \({\mathbb {W}}_{m}\) should satisfy the following condition

$$\begin{aligned}&\displaystyle \cup _{i=1}^{l} \mathscr {K}_{m_{i}}(A,B,\sigma _{i}) \subseteq \textit{Range}({\mathbb {V}}_{m})\\&\displaystyle \cup _{i=1}^{l} \mathscr {K}_{m_{i}}(A^{T},C^{T},\sigma _{i}) \subseteq \textit{Range}({\mathbb {W}}_{m}) \end{aligned}$$

where \(\displaystyle \sum _{i=1}^{l} m_{i}=m\), for that the multipoint rational interpolation problem (8) is solved.

In the rational block Lanczos-type algorithm (Algorithm 2), steps 8-9 and steps 18-19 are used to generate the next Lanczos vectors. According to Algorithm 2, two residual expressions are used. At each iteration k, we used a new interpolation point \(\sigma _{k+1}, k=1,\ldots ,m-1\) and we initialize the subsequent Krylov subspaces corresponding to this shift by \( S_{k}=(A-\sigma _{k+1}I_{n})^{-1}V_{k}\) and \(R_{k}=(A-\sigma _{k+1}I_{n})^{-T}W_{k}\) if \(\sigma _{k+1}\) is finite and \(S_{k}=AV_{k}, R_{k}=A^{T}W_{k}\) if \(\sigma _{k+1}=\infty \).

To insure that the block vectors \(V_{k+1}\) and \(W_{k+1}\) generated in each iteration are biorthogonal, the QR and SVD decompositions are used (steps 12–14 and 22–24). The matrices \(H_{k}\) and \(G_{k}\) constructed in steps 10 and 20 are \(kp \times p\) and they are used to construct the block upper Hessenberg matrices \(\mathbb {H}_{m}\) and \(\mathbb {G}_{m}\), respectively (for more details see Theorem 2).

We notice that a breakdown may occur in Algorithm 2 if the smallest singular value of \(W_{k+1}^{T}V_{k+1}\) is zero, which causes a problem in the calculating of the block \(V_{k+1}\) and \(W_{k+1}\). In [4], a novel breakdown treatment scheme was proposed to overcome this problem for the single point block Lanczos algorithm ABLE. This method is generalized in [26] for MABLE algorithm. Here, the same technique could be used to detect and cure breakdowns. However, this problem of breakdown or near-breakdown is not developed in this paper.

Next, we give a theorem that establishes the rational Lanczos equations that relate \(A, {\mathbb {V}}_{m}, {\mathbb {W}}_{m}\) and the Hessenberg matrices constructed by Algorithm 2.

Theorem 2

Let \({\mathbb {V}}_{m+1}\) and \({\mathbb {W}}_{m+1}\) be the matrices generated by Algorithm 2, assuming that A is nonsingular and that all the interpolation points \(\sigma _{i}, \, i=1,\ldots ,m+1\) are finite real numbers. Then, there exist \((m+1)p \times mp\) block upper Hessenberg matrices \(\widetilde{\mathbb {H}}_{m}, \widetilde{\mathbb {G}}_{m}, \widetilde{\mathbb {K}}_{m}\) and \(\widetilde{\mathbb {L}}_{m}\)such that the following relations hold for the left and the right Krylov subspaces:

$$\begin{aligned} A{\mathbb {V}}_{m+1} \widetilde{\mathbb {H}}_{m}= & {} {\mathbb {V}}_{m+1} \widetilde{\mathbb {K}}_{m} \end{aligned}$$
(9)
$$\begin{aligned} A^{T}{\mathbb {W}}_{m+1}{}\widetilde{\mathbb {G}}_{m}= & {} {\mathbb {W}}_{m+1}\widetilde{\mathbb {L}}_{m}, \end{aligned}$$
(10)
$$\begin{aligned} \mathbb {H}_{m}= & {} {\mathbb {W}}_{m}^{T}A^{-1}{\mathbb {V}}_{m} \mathbb {K}_{m}, \end{aligned}$$
(11)
$$\begin{aligned} \mathbb {G}_{m}= & {} {\mathbb {V}}_{m}^{T}A^{-T}{\mathbb {W}}_{m} \mathbb {L}_{m}, \end{aligned}$$
(12)

where \(\mathbb {H}_{m}\), \(\mathbb {G}_{m}\), \(\mathbb {K}_{m}\) and \(\mathbb {L}_{m}\) are the \(mp \times mp\) block upper Hessenberg matrices obtained by deleting the last row block vectors of \(\widetilde{\mathbb {H}}_{m}, \widetilde{\mathbb {G}}_{m}, \widetilde{\mathbb {K}}_{m}\) and \(\widetilde{\mathbb {L}}_{m}\), respectively.

Proof

We begin by the case where \(k=1,\ldots ,m-1\) which involves the execution of Step 9. Replacing the expression of \(S_{k}\) into the expressions of Step 11 and Step 12 yields the following relation

$$\begin{aligned} V_{k+1}H_{k+1,k}=(A-\sigma _{k+1}I_{n})^{-1}V_{k}-{\mathbb {V}}_{k}H_{k} \end{aligned}$$

which can be written as

$$\begin{aligned}{}[{\mathbb {V}}_{k} \ V_{k+1}]\left[ \begin{array}{c} H_{k} \\ H_{k+1,k} \\ \end{array}\right] =(A-\sigma _{k+1}I_{n})^{-1}V_{k}. \end{aligned}$$
(13)

Multiplying (13) on the left by \((A-\sigma _{k+1}I_{n})\) and replacing \(V_{k}\) by \({\mathbb {V}}_{k}E_{k}\) gives

$$\begin{aligned} (A-\sigma _{k+1}I_{n}) {\mathbb {V}}_{k+1}\left[ \begin{array}{c} H_{k} \\ H_{k+1,k} \\ \end{array}\right] ={\mathbb {V}}_{k}E_{k}, \end{aligned}$$

where \(E_{k}\) is an \(kp \times p\) tall thin matrix with an identity matrix of dimension p at the \(k^{th}\) block and zero elsewhere. Re-arranging the expression of the last equation as

$$\begin{aligned} A {\mathbb {V}}_{k+1} \left[ \begin{array}{c} H_{k} \\ H_{k+1,k} \\ \end{array}\right] = {\mathbb {V}}_{k+1} \left( \left[ \begin{array}{c} E_{k} \\ 0 \\ \end{array}\right] +\sigma _{k+1} \left[ \begin{array}{c} H_{k} \\ H_{k+1,k} \\ \end{array}\right] \right) ,\, k=1,\ldots ,m-1. \end{aligned}$$
(14)

On the other hand, for \(k=1,\ldots ,m-1\), we have

$$\begin{aligned} A {\mathbb {V}}_{m+1} = [A {\mathbb {V}}_{k+1}, AV_{k+2},\ldots ,AV_m,AV_{m+1} ]. \end{aligned}$$

Therefore, we can deduce from 14, the following expression

$$\begin{aligned} A {\mathbb {V}}_{m+1} \left[ \begin{array}{c} H_{k} \\ H_{k+1,k} \\ \mathbf{0}\\ \end{array}\right] = {\mathbb {V}}_{m+1} \left( \left[ \begin{array}{c} E_{k} \\ 0 \\ \mathbf{0}\\ \end{array}\right] +\sigma _{k+1} \left[ \begin{array}{c} H_{k} \\ H_{k+1,k} \\ \mathbf{0}\\ \end{array}\right] \right) , \end{aligned}$$
(15)

where \(\mathbf{0}\) is the zero matrix having \(m-k\) rows.

Now, consider the case where \(k=m\). Using steps 19-21 gives the following relation

$$\begin{aligned} V_{m+1}H_{m+1,m}=A^{-1}B-{\mathbb {V}}_{m}H_{m} \end{aligned}$$
(16)

Since \((A-\sigma _{1}I_{n})^{-1}B=V_{1}H_{1,0}\) and \(V_{1}={\mathbb {V}}_{m}E_{1}\), (16) can be rewritten as

$$\begin{aligned} {\mathbb {V}}_{m+1}\left[ \begin{array}{c} H_{m} \\ H_{m+1,m} \\ \end{array}\right] =A^{-1}(A-\sigma _{1}I_{n}){\mathbb {V}}_{m}E_{1}H_{1,0}. \end{aligned}$$

Multiplying on the left by A and rearranging the expression results in

$$\begin{aligned} A {\mathbb {V}}_{m+1} \left( \left[ \begin{array}{c} H_{m} \\ H_{m+1,m} \\ \end{array}\right] - \left[ \begin{array}{c} E_{1} \\ 0 \\ \end{array}\right] H_{1,0} \right) = {\mathbb {V}}_{m+1} \left( -\sigma _{1} \left[ \begin{array}{c} E_{1} \\ 0 \\ \end{array}\right] H_{1,0} \right) \end{aligned}$$
(17)

Equations (15) and (17) can be expressed lead to the following expression

$$\begin{aligned} A{\mathbb {V}}_{m+1} \widetilde{\mathbb {H}}_{m}={\mathbb {V}}_{m+1}\widetilde{\mathbb {K}}_{m}, \end{aligned}$$
(18)

where \(\widetilde{\mathbb {H}}_{m}\) and \(\widetilde{\mathbb {K}}_{m}\) are the block upper Hessenberg matrices of \({\mathbb {R}}^{(m+1)p\times mp}\), given as follows

$$\begin{aligned} \widetilde{\mathbb {H}}_{m}= & {} [\widetilde{\mathbb {H}}^{(1)},\widetilde{\mathbb {H}}^{(2)},\ldots ,\widetilde{\mathbb {H}}^{(m)} ]\;\;\mathrm{and} \\ \widetilde{\mathbb {K}}_{m}= & {} [\widetilde{\mathbb {K}}^{(1)},\widetilde{\mathbb {K}}^{(2)},\ldots ,\widetilde{\mathbb {K}}^{(m)} ], \end{aligned}$$

where for \(k=1,\ldots ,m-1\) the k-th block columns are given by

$$\begin{aligned} \widetilde{\mathbb {H}}^{(k)}= \left[ \begin{array}{c} H_{k} \\ H_{k+1,k} \\ \mathbf{0}\\ \end{array}\right] \; \mathrm{and} \; \widetilde{\mathbb {K}}^{(k)} = \left[ \begin{array}{c} E_{k} + \sigma _{k+1} H_{k} \\ \sigma _{k+1} H_{k+1,k} \\ \mathbf{0}\\ \end{array}\right] \end{aligned}$$

and for \(k=m\) we have

$$\begin{aligned} \widetilde{\mathbb {H}}^{(m)}= \left[ \begin{array}{c} H_{m} -E_{1} H_{1,0} \\ H_{m+1,m} \\ \end{array}\right] \;\; \mathrm{and} \;\; \widetilde{\mathbb {K}}^{(m)} =\left[ \begin{array}{c} -\sigma _{1} E_{1} H_{1,0} \\ 0 \\ \end{array}\right] \end{aligned}$$

Equation (11) is easily derived from the relation (9).

In a similar way, we can show the relations (10) and (12) for the left Krylov subspace.

We notice that since \(\widetilde{\mathbb {K}}^{(m)} =\left[ \begin{array}{l} \mathbb {K}^{(m)} \\ 0 \\ \end{array}\right] \), and \(A{\mathbb {V}}_{m+1} =[A{\mathbb {V}}_{m}, AV_{m+1} ]\) it follows that

$$\begin{aligned} A{\mathbb {V}}_{m+1} \widetilde{\mathbb {H}}_{m} = {\mathbb {V}}_{m} \mathbb {K}_{m}. \end{aligned}$$
(19)

In the same manner, we also have

$$\begin{aligned} A^T{\mathbb {W}}_{m+1} \widetilde{\mathbb {G}}_{m} = {\mathbb {W}}_{m} \mathbb {L}_{m}. \end{aligned}$$
(20)

In what follows, we assume that all the shifts \(\sigma _{i}, \, i=1,\ldots ,m+1\) are finite real numbers. This was always the case in our numerical examples.

4 An Error Estimation for the Transfer Function

The computation of the exact transfer matrix error between the original and the reduced systems

$$\begin{aligned} \varepsilon (s)= H(s)-H_m(s) \end{aligned}$$
(21)

is important for the measure of the accuracy of the resulting reduced-order model. Unfortunately, the exact error \(\varepsilon (s)\) is not available, because the higher dimension of the original system yields the computation of H(s) very difficult. To remedy this situation, various approaches have been explored in the literature for estimating the error (21).

In [19], Grimme proposed the computation of the modelling error in term of two residual vectors in the case of single-input and single-output systems. The result is extended here to the multi-input and multi-output case. Let

$$\begin{aligned} \left\{ \begin{array}{lll} R_{B}(s) &{} = &{} B-(sI_{n}-A){\mathbb {V}}_{m}\tilde{X}_{B}(s),\\ R_{C}(s) &{} = &{} C^{T}-(sI_{n}-A)^{T}{\mathbb {W}}_{m}\tilde{X}_{C}(s)\\ \end{array} \right. \end{aligned}$$

be the residual expressions, where \(\tilde{X}_{B}(s)\) and \(\tilde{X}_{C}(s)\) are the solutions of the matrix equations

$$\begin{aligned} \left\{ \begin{array}{c c c} (sI_{mp}-A_m) \tilde{X}_{B}(s) &{} = &{}B_m,\\ (sI_{mp}-A_m)^{T} \tilde{X}_{C}(s) &{} = &{}C_m^{T},\\ \end{array} \right. \end{aligned}$$

and satisfy the Petrov-Galerkin conditions

$$\begin{aligned} \left\{ \begin{array}{c c c} R_{B}(s) &{} \bot &{} \mathrm{Range}({W}_{1} ,\ldots ,{W}_{m} )\\ R_{C}(s) &{} \bot &{} \mathrm{Range} ({V}_{1} ,\ldots ,{V}_{m}) ,\\ \end{array} \right. \end{aligned}$$

which means that \( {\mathbb {W}}_{m}^{T}R_{B}(s)={\mathbb {V}}_{m}^{T}R_{C}(s)=0\). In the following theorem, we give an expression of the error \(\varepsilon (s)\).

Theorem 3

The error between the frequency responses of the original and reduced-order systems can be expressed as

$$\begin{aligned} \varepsilon (s)=R_{C}^{T}(s)(sI_{n}-A)^{-1}R_{B}(s). \end{aligned}$$
(22)

The proof of this theorem is similar to the one of Theorem 5.1 given in [19] for single-input and single-output system. In [5], a new matrix-based derivation of the error between the original system and the rational interpolation resulting is proposed using the PVL (Padé Via Lanczos) method.

In the following, we compute an error estimation using our rational block Lanczos-type algorithm and the derived rational Lanczos equations. In the previous section we defined the rational block Krylov subspaces by (6) and (7). However, the inclusion of the block vectors B and \(C^{T}\) may be beneficial. Then for computing an error estimation, we use the following rational Krylov subspaces

$$\begin{aligned} \mathscr {K}_{m}(A,B,\Sigma _m^{\prime })= & {} \mathrm{Range} \left\{ B,(A-\sigma _{2}I_n)^{-1}B, \ldots ,\prod _{k=2}^{m} (A-\sigma _{k}I_n)^{-1}B \right\} , \end{aligned}$$
(23)
$$\begin{aligned} \mathscr {K}_{m}(A^{T},C^{T},\Sigma _m^{\prime })= & {} \mathrm{Range} \left\{ C^{T},(A-\sigma _{2}I_n)^{-T}C^{T}, \ldots ,\prod _{k=2}^{m}(A-\sigma _{k}I_n)^{-T}C^{T} \right\} ,\quad \end{aligned}$$
(24)

where \(\Sigma _m^{\prime }=\{\sigma _{2},\ldots ,\sigma _{m}\}\) is the set of interpolation points. Thus we have the following theorem.

Theorem 4

Let \({\mathbb {V}}_{m}\) and \({\mathbb {W}}_{m}\) be the matrices computed using the rational block Lanczos algorithm. If \((sI_{n}-A)\) and \((sI_{mp}-A_m)\) are nonsingular, we have

$$\begin{aligned} H(s)-H_m(s)=C(sI_{n}-A)^{-1}({\mathbb {V}}_{m}{\mathbb {W}}_{m}^{T}-I_{n}) AV_{m+1}H_{m+1,m}E_{m}^{T}\mathbb {H}_{m}^{-1}(sI_{mp}-A_m)^{-1}B_m. \end{aligned}$$
(25)

Proof

The error between the initial and the projected transfer functions is given by

$$\begin{aligned} H(s)-H_m(s) = C(sI_{n}-A)^{-1} \left( B-(sI_{n}-A) {\mathbb {V}}_{m}(sI_{mp}-A_m)^{-1} B_m\right) . \end{aligned}$$

Since

$$\begin{aligned} A{\mathbb {V}}_{m+1} \widetilde{\mathbb {H}}_{m} = {\mathbb {V}}_{m} \mathbb {K}_{m}, \end{aligned}$$
(26)

then

$$\begin{aligned} A {\mathbb {V}}_{m} = \left( {\mathbb {V}}_{m} \mathbb {K}_{m}-AV_{m+1}H_{m+1,m}E_{m}^{T}\right) \mathbb {H}_{m}^{-1} \end{aligned}$$
(27)

and

$$\begin{aligned} A_m = {\mathbb {W}}_{m}^{T}A {\mathbb {V}}_{m}=(\mathbb {K}_{m}-{\mathbb {W}}_{m}^{T}AV_{m+1}H_{m+1,m}E_{m}^{T})\mathbb {H}^{-1}_{m}. \end{aligned}$$
(28)

Using equations (27) and (28), we obtain

$$\begin{aligned} (sI_{n}- A){\mathbb {V}}_{m} = {\mathbb {V}}_{m}(sI_{mp}-A_m)-\Gamma _{m}, \end{aligned}$$

where

$$\begin{aligned} \Gamma _{m}=\left( {\mathbb {V}}_{m}{\mathbb {W}}_{m}^{T}-I_{n}\right) AV_{m+1}H_{m+1,m}E_{m}^{T}\mathbb {H}_m^{-1}. \end{aligned}$$

The relation (25) can be obtained using this result and the fact that \({\mathbb {V}}_{m} {\mathbb {W}}_{m}^{T}B=B\).

4.1 Residual Error Expressions for the Rational Lanczos Algorithm

In [12] simple Lanczos equations for the standard rational case are proposed and used for deriving simple residual error-expressions. In this section, we use the rational Lanczos equations given in Theorem 3.2 to simplify the residual error expressions. To simplify calculations, we use the rational Krylov subspaces in (23) and (24). Using the rational Lanczos equations and the fact that \(B\in \mathscr {K}_{m}(A,B,\Sigma _m^{\prime }), C^{T}\in \mathscr {K}_{m}(A^{T},C^{T},\Sigma _m^{\prime })\), the expressions of the residual \(R_{B}(s)\) and \(R_{C}(s)\) could be written as

$$\begin{aligned} R_{B}(s)= & {} B-(sI_n-A) {\mathbb {V}}_{m} (sI_{mp}-A_m)^{-1}B_m \nonumber \\= & {} \underbrace{\left( {\mathbb {V}}_{m} {\mathbb {W}}_{m}^{T}-I\right) AV_{m+1}}_{\tilde{B}} \underbrace{H_{m+1,m}E_{m}^{T} \mathbb {H}_m^{-1}\left( sI_{mp}-A_m\right) ^{-1}B_m}_{\tilde{R}_{B}(s)} \end{aligned}$$
(29)
$$\begin{aligned} R_{C}(s)= & {} C^{T}-(sI-A)^{T}{\mathbb {W}}_{m} (sI_{mp}-A_m)^{-T}C_m^{T} \nonumber \\= & {} \underbrace{\left( {\mathbb {W}}_{m} {\mathbb {V}}_{m}^{T}-I\right) A^{T}W_{m+1}}_{\tilde{C}^{T}} \underbrace{G_{m+1,m}E_{m}^{T} \mathbb {G}_{m}^{-1}\left( sI_{mp}-A_m\right) ^{-T}C_m^{T}}_{\tilde{R}_{C}(s)}, \end{aligned}$$
(30)

where \(\tilde{R}_{B}(s)\), \(\tilde{R}_{C}(s)\) are the terms of the residual errors \(R_{B}(s)\) and \(R_{C}(s)\), respectively, depending on the frequencies. The matrices \(\tilde{B}\), \(\tilde{C}^{T}\) are frequency-independent terms of \(R_{B}(s)\) and \(R_{C}(s)\), respectively. Therefore, the error expression in (22) becomes

$$\begin{aligned} \varepsilon (s) = \tilde{R}_{C}(s)^{T} \tilde{C}(sI_{n}-A)^{-1} \tilde{B} \tilde{R}_{B}(s) = \tilde{R}_{C}(s)^{T} \tilde{H}(s) \tilde{R}_{B}(s). \end{aligned}$$
(31)

The transfer function \(\tilde{H}(s)=\tilde{C}(sI_{n}-A)^{-1} \tilde{B}\) contains terms related to the original system which makes the computation of \(\Vert \tilde{R}_{C}^{T}\tilde{H}\tilde{R}_{B} \Vert _{\infty } \) very expensive. Then, instead of using \(\tilde{H}(s)\) we can use an approximation of \(\tilde{H}(s)\). Various possible approximations of the error \(\varepsilon (s)\) are listed in Table 1.

Table 1 Estimations of the error \(\varepsilon (s)\)
Full size table

5 An Adaptive-Order Rational Block Lanczos-Type Algorithm

Model-order reduction using multipoint rational interpolation generally gives a more accurate reduced-order model than interpolation around a single point. Unfortunately, the selection of interpolation points is not an automated process and it requires an adequate choice for more accurate rational Krylov subspace. In [7, 22] the Iterative Rational Krylov Algorithm (IRKA) has been proposed in the context of the \({{\mathscr {H}}}_{2}\)-optimal model-order reduction by using a specific way to choose the interpolation points \(\sigma _{i}\), \(i=1,\ldots ,m\). Starting from an initial set of interpolation points, a reduced-order system is determined and a new set of interpolation points is chosen as the Ritz values \(-\lambda _{i}(A_m), i=1,\ldots ,m\), where \(\lambda _{i}(A_m)\) are the eigenvalues of \(A_m\). The process continues until the Ritz values from consecutive reduced-order models stagnate.

In [9, 10, 20, 25, 30] some techniques for choosing good interpolation points have been proposed. The aim of these methods is the construction of the next interpolation point at every step and they are based on the idea that the shifts should be selected such that the norm of certain approximation of the errors should be minimized at every iteration. Here, an adaptive approach is proposed by using the following error-approximation expression

$$\begin{aligned} \hat{\varepsilon }(s)=\tilde{R}_{C}^{T}(s)\tilde{R}_{B}(s). \end{aligned}$$

Then the next shift \(\sigma _{k+1} \in {\mathbb {R}}\) is selected as

$$\begin{aligned} {\tilde{\sigma }}_{k+1}= \mathrm{arg} \max _{s \in S} \Vert \tilde{R}_{C}^{T}(s)\tilde{R}_{B}(s) \Vert _{2}, \end{aligned}$$
(32)

and if \(\tilde{\sigma }_{k+1}\) is complex, its real part is retained and used as the next interpolation point.

Remark 2

The choice of the approximated error expression \(\hat{\varepsilon }(s)=\tilde{R}_{C}^{T}(s)\tilde{R}_{B}(s)\) is a heuristic choice that allowed to have good shifts without much calculations as it is shown in the numerical tests. We notice that for small problems, one can also use the following criterion for selecting the shifts

$$\begin{aligned} \sigma _{k+1}= \mathrm{arg} \max _{s \in S} \Vert {R}_{C}^{T}(s) {R}_{B}(s) \Vert _{2}, \end{aligned}$$
(33)

This selection gives good results but, at it is related to the dimension n of the space, it needs more computation times and arithmetic operations for large problems. In our numerical examples, we used (32) for large dimensions and (33) for small problems.

An adaptive order rational block Lanczos algorithm for the computation of the reduced-order system using the rational block Lanczos process (Algorithm 2) and the above adaptive approach for selecting the interpolation points can be summarized as follows.

figure c

Notice that, for choosing the interpolation points, we can also use one of the approximated error expressions listed in Table 1. The way of choosing these parameters affects the speed of convergence of the algorithm.

Remark 3

For large problems, the total number of arithmetic operations after m iterations is dominated by \(\mathscr { O}(mpn^2)\) and also LU factorizations for solving shifted linear systems with the shifted matrices \(A-\sigma _i I_n\) (Line 3 and Line 9 of Algorithm 2). One can also use solvers such as GMRES with a preconditioner for solving these shifted linear systems.

6 Numerical Experiments

In this section, we give some experimental results to show the effectiveness of the proposed approaches. All the experiments were performed on a computer of Intel Core i5 at 1.3GHz and 8GB of RAM. The algorithms were coded in Matlab 8.0. We give some numerical tests to show the performance of the adaptive-order rational block Lanczos-type (AORBL) algorithm. In all the presented experiments, \(tol=10^{-8}\) and the (AORBL) algorithm is stopped when the \(H_{\infty }\)-error

$$\begin{aligned} err=\Vert H_m-H_{m-1} \Vert _{\infty } \end{aligned}$$

between the previous reduced system and the current one is less than tol, where the \(H_{\infty }\)-norm of the error is given as (cf., e.g., [2], sect. 5.3)

$$\begin{aligned} \Vert H_m-H_{m-1} \Vert _{\infty }=\sup _{\omega \in {\mathbb {R}}} \Vert H_m(j \omega )-H_{m-1}(j \omega ) \Vert _{2}, \end{aligned}$$

where \(\omega \in [10^{-3},10^{3}]\) and \(j=\sqrt{-1}\).

To compute the \(H_{\infty }\)-norm, the following functions from LYAPACK [28] are used :

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

  • lp_para: Used for computing the initial first two shifts.

  • lp_gnorm: Computes \(\Vert H_m(j \omega )-H_{m-1}(j \omega ) \Vert _{2}\).

In our experiments, we used some matrices from LYAPACK . These matrix tests are reported in the following Table 2. For the FOM model, we notice that originally, the model is 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}], \quad \ C^{T}=[c_{1},\ldots ,c_{6}], \end{aligned}$$

where

$$\begin{aligned} b_{1}^{T}=c_{1}=(\underbrace{10,\ldots ,10}_{6}, \underbrace{1,\ldots ,1}_{1000}), \quad \textit{and} \quad b_{2},\ldots ,b_{6}; c_{2},\ldots ,c_{6} \end{aligned}$$

are random column vectors.

Table 2 The matrix tests
Full size table

For the fdm model, the corresponding matrix A is obtained from the centred 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} \left\{ \begin{array}{c c c} f(x,y) &{} = &{} log(x+2y),\\ g(x,y) &{} = &{} e^{x+y},\\ h(x,y) &{} = &{} x+y,\\ \end{array} \right. \end{aligned}$$

and 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=200\) and the dimension of A is \(n = n_0^2=40.000\).

Example 1

For this experiment, we used the modified FOM model with \(m=18\). The left plots of Fig. 1 show the frequency response of the original system (circles) compared to the frequency response of its approximation (solid plot). The right plot of this figure represents the exact error \(\Vert H(j \omega )- H_m(j \omega ) \Vert _{2}\) for different frequencies.

Fig. 1
figure 1

Left \(\Vert {H(j \omega )} \Vert _{2}\) and it’s approximation \(\Vert H_m(j \omega ) \Vert _{2}\). Right the exact error \(\Vert H(j \omega )- H_m(j \omega ) \Vert _{2}\) for the modified FOM model with \(m=18\)

Full size image

Example 2

In this example, we considered the ISS model and we plotted the \(H_{\infty }\) error norm \(\Vert H-H_m \Vert _{\infty }\) versus the number m of iterations. As can be shown from this plot, the AORBL algorithm gives good result with small values of m (Fig. 2).

Fig. 2
figure 2

The \(H_{\infty }\) error \(\Vert H - H_m \Vert _{\infty }\) versus the number of iterations for the ISS model

Full size image

Example 3

We consider the well known CD player model. This is a small dimension example but generally difficult and is always considered as a benchmark test. The left plots of Fig. 3 represent the sigma plots of the original system (circles) and the reduced order system (solid line). In the right part, we plotted the error norm \(\Vert H(s) - H_m(s) \Vert _{2}\) versus the frequencies.

Fig. 3
figure 3

The CD player model with \(m=30\). Left The singular values of the exact transfer function (circles) and its approximation (solid) versus the frequencies. Right The error norms \(\Vert H(s) - H_m(s) \Vert _{2}\)

Full size image

Example 4

In the last example we compared the AORBL algorithm with IRKA. We used four models: the CD player, the ISS, the Rail3113 and the fdm model (\(n=40000\), \(p=5\)). In Table 3, we listed the obtained \(H_{\infty }\) norm of the error transfer function \(\Vert H-H_m \Vert _{\infty }\), the corresponding cpu-time, the number of required iterations for the two methods and in parentheses we also gave the used space dimension for IRKA. A maximum number of \(m_{max}= 500\) iterations was allowed to the two algorithms. As observed from Table 3, IRKA and AORBL returns similar results (computing times and norms of the errors) for the first two models with an advantage for AORBL. However, for the last two examples, IRKA didn’t converge within the allowed maximum number of iterations.

Table 3 Comparison between IRKA and AORBL for CD player, ISS, Rail3113 and fdm models
Full size table

7 Conclusion

In this paper, we proposed a new adaptive rational block Lanczos process and an adaptive method for choosing the interpolation points with applications in model order reduction of multi-input and multi-output first-order stable linear dynamical systems. Moreover, we derived new Lanczos-like expressions and new error estimations between the original and the reduced transfer functions. We presented some numerical results to confirm the good performance of the rational block Lanczos subspace method compared with other known methods. The proposed procedure is tested on well known benchmark problems of medium and large dimensions and the numerical results show that the adaptive approach allows one to obtain reduced order models of small dimension.