Iterative rational Krylov algorithm

The iterative rational Krylov algorithm (IRKA), is an iterative algorithm, useful for model order reduction (MOR) of single-input single-output (SISO) linear time-invariant dynamical systems. At each iteration, IRKA does an Hermite type interpolation of the original system transfer function. Each interpolation requires solving $r$ shifted pairs of linear systems, each of size $n\times n$; where $n$ is the original system order, and $r$ is the desired reduced model order (usually $r\ll n$). The algorithm was first introduced by Gugercin, Antoulas and Beattie in 2008. It is based on a first order necessary optimality condition, initially investigated by Meier and Luenberger in 1967. The first convergence proof of IRKA was given by Flagg, Beattie and Gugercin in 2012, for a particular kind of systems.

MOR as an optimization problem

Consider a SISO linear time-invariant dynamical system, with input $v(t)$, and output $y(t)$:

$\{\begin{array}{l}\dot{x}(t)=Ax(t)+bv(t)\\ y(t)=c^{T}x(t)\end{array}A\in {\mathbb{ℝ}}^{n\times n},b,c\in {\mathbb{ℝ}}^n,v(t),y(t)\in \mathbb{ℝ},x(t)\in {\mathbb{ℝ}}^n.$

Applying the Laplace transform, with zero initial conditions, we obtain the transfer function $G$, which is a fraction of polynomials:

$G(s)=c^T(sI-A{)}^{-1}b,A\in {\mathbb{ℝ}}^{n\times n},b,c\in {\mathbb{ℝ}}^n.$

Assume $G$ is stable. Given $r<n$, MOR tries to approximate the transfer function $G$, by a stable rational transfer function $G_r$, of order $r$:

$G_r(s)=c_r^T(s{I}_r-A_r{)}^{-1}{b}_r,A_r\in {\mathbb{ℝ}}^{r\times r},b_r,c_r\in {\mathbb{ℝ}}^r.$

A possible approximation criterion is to minimize the absolute error in $H_2$ norm:

$G_r\in \underset{\dim (\hat{G})=r,\hat{G}\text{ stable}}{\mathrm{a}\mathrm{r}\mathrm{g}\min }\Vert G-\hat{G}{\Vert }_{H_2},\Vert G{\Vert }_{H_2}^2:=\frac{1}{2\pi }\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}|G(ja){|}^{2}da.$

This is known as the $H_2$ optimization problem. This problem has been studied extensively, and it is known to be non-convex; which implies that usually it will be difficult to find a global minimizer.

Meier–Luenberger conditions

The following first order necessary optimality condition for the $H_2$ problem, is of great importance for the IRKA algorithm.

Theorem ([Theorem 3.4] [Theorem 1.2]) —  Assume that the $H_2$ optimization problem admits a solution $G_r$ with simple poles. Denote these poles by: ${\lambda }_1(A_r),\dots ,{\lambda }_r(A_r)$. Then, $G_r$ must be an Hermite interpolator of $G$, through the reflected poles of $G_r$:

$G_r({\sigma }_i)=G({\sigma }_i),G_r^{\prime }({\sigma }_i)=G^{\prime }({\sigma }_i),{\sigma }_i=-{\lambda }_i(A_r),\mathrm{\forall }i=1,\dots ,r.$

Note that the poles ${\lambda }_i(A_r)$ are the eigenvalues of the reduced $r\times r$ matrix $A_r$.

Hermite interpolation

An Hermite interpolant $G_r$ of the rational function $G$, through $r$ distinct points ${\sigma }_1,\dots ,{\sigma }_r\in \mathbb{ℂ}$, has components:

$A_r=W_r^{*}A{V}_r,b_r=W_r^{*}b,c_r=V_r^{*}c,A_r\in {\mathbb{ℝ}}^{r\times r},b_r\in {\mathbb{ℝ}}^r,c_r\in {\mathbb{ℝ}}^r;$

where the matrices $V_r=(v_1\mid \dots \mid v_r)\in {\mathbb{ℂ}}^{n\times r}$ and $W_r=(w_1\mid \dots \mid w_r)\in {\mathbb{ℂ}}^{n\times r}$ may be found by solving $r$ dual pairs of linear systems, one for each shift [Theorem 1.1]:

$({\sigma }_{i}I-A)v_i=b,({\sigma }_{i}I-A{)}^{*}{w}_i=c,\mathrm{\forall }i=1,\dots ,r.$

IRKA algorithm

As can be seen from the previous section, finding an Hermite interpolator $G_r$ of $G$, through $r$ given points, is relatively easy. The difficult part is to find the correct interpolation points. IRKA tries to iteratively approximate these "optimal" interpolation points.

For this, it starts with $r$ arbitrary interpolation points (closed under conjugation), and then, at each iteration $m$, it imposes the first order necessary optimality condition of the $H_2$ problem:

1. find the Hermite interpolant $G_r$ of $G$, through the actual $r$ shift points: ${\sigma }_1^m,\dots ,{\sigma }_r^m$.

2. update the shifts by using the poles of the new $G_r$: ${\sigma }_i^{m+1}=-{\lambda }_i(A_r),\mathrm{\forall }i=1,\dots ,r.$

The iteration is stopped when the relative change in the set of shifts of two successive iterations is less than a given tolerance. This condition may be stated as:

$\frac{|{\sigma }_i^{m+1}-{\sigma }_i^m|}{|{\sigma }_i^m|}<\text{tol},\mathrm{\forall }i=1,\dots ,r.$

As already mentioned, each Hermite interpolation requires solving $r$ shifted pairs of linear systems, each of size $n\times n$:

$({\sigma }_i^{m}I-A)v_i=b,({\sigma }_i^{m}I-A{)}^{*}{w}_i=c,\mathrm{\forall }i=1,\dots ,r.$

Also, updating the shifts requires finding the $r$ poles of the new interpolant $G_r$. That is, finding the $r$ eigenvalues of the reduced $r\times r$ matrix $A_r$.

Pseudocode

The following is a pseudocode for the IRKA algorithm [Algorithm 4.1].

algorithm IRKA
    input: $A,b,c$, $\text{tol}>0$, ${\sigma }_1,\dots ,{\sigma }_r$ closed under conjugation
        $({\sigma }_{i}I-A)v_i=b,\mathrm{\forall }i=1,\dots ,r$ % Solve primal systems
        $({\sigma }_{i}I-A{)}^{*}{w}_i=c,\mathrm{\forall }i=1,\dots ,r$ % Solve dual systems

    while relative change in {${\sigma }_i$} > tol
        $A_r=W_r^{*}A{V}_r$ % Reduced order matrix
        ${\sigma }_i=-{\lambda }_i(A_r),\mathrm{\forall }i=1,\dots ,r$ % Update shifts, using poles of $G_r$
        $({\sigma }_{i}I-A)v_i=b,\mathrm{\forall }i=1,\dots ,r$ % Solve primal systems
        $({\sigma }_{i}I-A{)}^{*}{w}_i=c,\mathrm{\forall }i=1,\dots ,r$ % Solve dual systems
    end while

    return $A_r=W_r^{*}A{V}_r,b_r=W_r^{*}b,c_r^T=c^T{V}_r$ % Reduced order model

Convergence

A SISO linear system is said to have symmetric state space (SSS), whenever: $A=A^T,b=c.$ This type of systems appear in many important applications, such as in the analysis of RC circuits and in inverse problems involving 3D Maxwell's equations. For SSS systems with distinct poles, the following convergence result has been proven: "IRKA is a locally convergent fixed point iteration to a local minimizer of the $H_2$ optimization problem."

Although there is no convergence proof for the general case, numerous experiments have shown that IRKA often converges rapidly for different kind of linear dynamical systems.

Extensions

IRKA algorithm has been extended by the original authors to multiple-input multiple-output (MIMO) systems, and also to discrete time and differential algebraic systems [Remark 4.1].

See also

Model order reduction

External links

• Model Order Reduction Wiki