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.
[1] At each iteration, IRKA does an Hermite type interpolation of the original system transfer function.
shifted pairs of linear systems, each of size
is the desired reduced model order (usually
The algorithm was first introduced by Gugercin, Antoulas and Beattie in 2008.
[2] It is based on a first order necessary optimality condition, initially investigated by Meier and Luenberger in 1967.
[3] The first convergence proof of IRKA was given by Flagg, Beattie and Gugercin in 2012,[4] for a particular kind of systems.
Consider a SISO linear time-invariant dynamical system, with input
: Applying the Laplace transform, with zero initial conditions, we obtain the transfer function
, MOR tries to approximate the transfer function
, by a stable rational transfer function
: A possible approximation criterion is to minimize the absolute error in
This problem has been studied extensively, and it is known to be non-convex;[4] which implies that usually it will be difficult to find a global minimizer.
problem, is of great importance for the IRKA algorithm.
optimization problem admits a solution
dual pairs of linear systems, one for each shift [4][Theorem 1.1]: As can be seen from the previous section, finding an Hermite interpolator
The difficult part is to find the correct interpolation points.
IRKA tries to iteratively approximate these "optimal" interpolation points.
arbitrary interpolation points (closed under conjugation), and then, at each iteration
, it imposes the first order necessary optimality condition of the
problem: 1. find the Hermite interpolant
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: As already mentioned, each Hermite interpolation requires solving
shifted pairs of linear systems, each of size
: Also, updating the shifts requires finding the
A SISO linear system is said to have symmetric state space (SSS), whenever:
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.
[4] For SSS systems with distinct poles, the following convergence result has been proven:[4] "IRKA is a locally convergent fixed point iteration to a local minimizer of the
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.
[1][4] 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 [1][2][Remark 4.1].