Moment-matching method

Description

The moment-matching methods are also called the Krylov subspace methods [1], as well as Padé approximation methods [2]. These methods are applicable for non-parametric linear time invariant systems, often the descriptor systems, e.g.

$E \frac{dx(t)}{dt}=A x(t)+B u(t), \quad y(t)=Cx(t), \quad \quad (1)$

They are very efficient in many engineering applications, circuit simulation, Microelectromechanical systems(MEMS) simulation, etc..

The basic steps are as follows. First, the transfer function

$H(s)=Y(s)/U(s)=C(sE-A)^{-1}B$

is expanded into a power series at an expansion point $s_0\in\mathbb{C}\cup \infty$.

Let $s=s_0+\sigma$, then, within the convergence radius of the series, we have

$H(s_0 + \sigma)= L^T[(s_{0}+\sigma){E}-A]^{-1}B$

$=L^T[\sigma { E}+(s_{0}{ E}-{ A})]^{-1}B$

$=L^T[{ I}-\sigma(s_0{ E}-{ A})^{-1}E]^{-1}[-(s_0{ E}-{ A})]^{-1}B$

$=L^T[{ I}+\sigma(s_0{ E}- A )^{-1}E+\sigma^2[(s_0{ E}-{ A})^{-1}]^{2}E+\ldots]\times \quad({ A}-s_0{E})^{-1}B$

$=\sum \limits^\infty_{i=0}\underbrace{L^T[(s_0{ E}-{A})^{-1}]^i({ A}-s_0{ E})^{-1}B}_{:= m_i(s_0)} \, \sigma^i,$

where $m_i(s_0)$ are called the moments of the transfer function about $s_0$ for $i=0,1,2,\ldots$. If the expansion point is chosen as zero then the moments simplify to $m_i(0)=L^\mathrm{T}(-A^{-1})^{i+1}B$. For $s_0=\infty$ the moments are also called Markov parameters which can be computed by $L^\mathrm{T} A^{i-1}B$.

The goal in moment-matching model reduction is the construction of a reduced order system where some moments $\hat m_i$ of the associated transfer function $\hat H$ match some moments of the original transfer function $H$.

The matrices $V$ and $W$ for model order reduction can be computed from the vectors which are associated with the moments, for example, using a single expansion point $s_0=0$, by

$\textrm{range}(V)=\textrm{span}\{{A}^{-1}B,({ A}^{-1})^2B, \ldots,({ A}^{-1})^{r}{B}\},$

$\textrm{range}(W)=\textrm{span}\{L, { A}^{-T}L,({ A}^{-T})^2L, \ldots ,({A}^{-T})^{r-1}L\}.$

The reduced model is in the form of the system in (2) in Projection based MOR. The corresponding transfer function $\hat H$ has good approximation properties around $s_0$, which matches the first $2r$ moments of $H(s)$ at $s_0$.

Using a set of $k$ distinct expansion points $\{s_1,\cdots,s_k\}$, the reduced model can be obtained by, e.g.,

$\textrm{range}(V)=\textrm{span}\{(A-s_1 {I})^{-1}B,\ldots,(A-s_k {I})^{-1}B \}$,

$\textrm{range}(W)=\textrm{span}\{(A-s_1 {I})^{-T}L,\ldots,(A-s_k {I})^{-T}L \},$

has order $r=k$ and matches the first two moments at each $s_j$, $j=1,\ldots,k$, see [3].

It can be seen that the columns of $V$, $W$ span Krylov subspaces which can easily be computed by Arnoldi or Lanczos methods [1][2]. In these algorithms only matrix-vector multiplications are used which are simple to implement and the complexity of the resulting methods is only $O(n r^2)$.

References

[1] R.W. Freund, Model reduction methods based on Krylov subspaces. Acta Numerica, 12:267-319, 2003.

[2] P. Feldmann and R.W. Freund, Efficient linear circuit analysis by Pade approximation via the Lanczos process. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 14:639-649, 1995.

[3] E.J. Grimme, Krylov projection methods for model reduction. PhD thesis, Univ. Illinois, Urbana-Champaign, 1997.