Abstract
Hankel-norm approximation is a model reduction method for linear time-invariant systems, which provides the best approximation in the Hankel semi-norm. In this paper, the computation of the optimal Hankel-norm approximation is generalized to the case of linear time-invariant continuous-time descriptor systems. A new algebraic characterization of all-pass descriptor systems is developed and used to construct an efficient algorithm by refining the generalized balanced truncation square root method. For a wide practical usage, adaptations of the introduced algorithm towards stable computations and sparse systems are suggested, as well as an approach for a projection-free algorithm. To show the approximation behavior of the introduced method, numerical examples are presented.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adamjan, V.M., Arov, D.Z., Kreı̆n, M.G.: Analytic properties of Schmidt pairs for a Hankel operator and the generalized Schur-Takagi problem. Mathematics of the USSR-Sbornik 15(1), 31–73 (1971). https://doi.org/10.1070/SM1971v015n01ABEH001531
Antoulas, A.C.: Approximation of large-scale dynamical systems, Adv. Des Control, vol. 6. SIAM Publications, Philadelphia (2005). https://doi.org/10.1137/1.9780898718713
Bai, Z., Demmel, J., Gu, M.: An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems. J Numer Math. 76(3), 279–308 (1997). https://doi.org/10.1007/s002110050264
Benner, P., Quintana-Ortí, E.S.: Model reduction based on spectral projection methods. In: Benner, P., Mehrmann, V., Sorensen, D. (eds.) Dimension Reduction of Large-Scale Systems, Lect. Notes Comput. Sci. Eng., vol. 45, pp 5–45. Springer, Berlin (2005), https://doi.org/10.1007/3-540-27909-1_1
Benner, P., Quintana-Ortí, E.S., Quintana-Ortí, G.: Parallel model reduction of large-scale linear descriptor systems via balanced truncation. In: Daydé, M., Dongarra, J.J., Hernández, V., Palma, J.M.L.M. (eds.) High Performance Computing for Computational Science - VECPAR 2004, Lecture Notes in Comput. Sci., vol. 3402, pp 340–353. Springer, Berlin (2005), https://doi.org/10.1007/11403937_27
Benner, P., Stykel, T.: Model order reduction for differential-algebraic equations: a survey. In: Ilchmann, A., Reis, T. (eds.) Surveys in Differential-Algebraic Equations IV, Differential-Algebraic Equations Forum, pp 107–160. Springer International Publishing, Cham (2017), https://doi.org/10.1007/978-3-319-46618-7_3
Benner, P., Werner, S.W.R.: MORLAB-3.0 – model order reduction laboratory. https://doi.org/10.5281/zenodo.842659. See also: https://www.mpi-magdeburg.mpg.de/projects/morlab (2017)
Benner, P., Werner, S.W.R.: On the transformation formulas of the Hankel-norm approximation. Proc Appl Math Mech. 17(1), 823–824 (2017). https://doi.org/10.1002/pamm.201710379
Benner, P., Werner, S.W.R.: Model reduction of descriptor systems with the MORLAB toolbox. IFAC-PapersOnLine 9th Vienna International Conference on Mathematical Modelling MATHMOD 2018, Vienna Austria, 21–23 February 2018 51 (2), 547–552 (2018). https://doi.org/10.1016/j.ifacol.2018.03.092
Cao, X., Saltik, M.B., Weiland, S.: Hankel model reduction for descriptor systems. In: 2015 54th IEEE Conference on Decision and Control (CDC), pp 4668–4673 (2015), https://doi.org/10.1109/CDC.2015.7402947
Freitas, F., Rommes, J., Martins, N.: Gramian-based reduction method applied to large sparse power system descriptor models. IEEE Trans Power Del. 23 (3), 1258–1270 (2008). https://doi.org/10.1109/TPWRS.2008.926693
Glover, K.: All optimal Hankel-norm approximations of linear multivariable systems and their L\(^{\infty }\)-error norms. Internat J. Control 39(6), 1115–1193 (1984). https://doi.org/10.1080/00207178408933239
Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2013)
Gugercin, S., Stykel, T., Wyatt, S.: Model reduction of descriptor systems by interpolatory projection methods. SIAM J. Sci. Comput. 35(5), B1010–B1033 (2013). https://doi.org/10.1137/130906635
Kågström, B., Van Dooren, P.: A generalized state-space approach for the additive decomposition of a transfer matrix. Numer. Lin. Alg. Appl. 1(2), 165–181 (1992)
Mehrmann, V., Stykel, T.: Balanced truncation model reduction for large-scale systems in descriptor form. In: Benner, P., Mehrmann, V., Sorensen, D.C. (eds.) Dimension Reduction of Large-Scale Systems, Lect. Notes Comput. Sci. Eng., vol. 45, pp 83–115. Springer, Berlin (2005), https://doi.org/10.1007/3-540-27909-1_3
Saak, J., Köhler, M., Benner, P.: M-M.E.S.S.-1.0.1 – the matrix equations sparse solvers library. https://doi.org/10.5281/zenodo.50575. See also: https://www.mpi-magdeburg.mpg.de/projects/mess (2016)
Schmidt, M.: Systematic discretization of input/output maps and other contributions to the control of distributed parameter systems. Ph.D. Thesis. Technische Universität, Berlin (2007). https://doi.org/10.14279/depositonce-1600
Sokolov, V.: Contributions to the minimal realization problem for descriptor systems. Dissertation, Fakultät für Mathematik, TU Chemnitz, Chemnitz (2006). http://nbn-resolving.de/urn:nbn:de:swb:ch1-200600965
Stewart, G.W., Sun, J.G.: Matrix Perturbation Theory. Academic Press, New York (1990)
Stykel, T.: Analysis and Numerical Solution of generalized Lyapunov equations. Dissertation, TU Berlin (2002). http://webdoc.sub.gwdg.de/ebook/e/2003/tu-berlin/stykel_tatjana.pdf
Stykel, T.: Gramian-based model reduction for descriptor systems. Math Control Signals Syst. 16(4), 297–319 (2004). https://doi.org/10.1007/s00498-004-0141-4
Stykel, T.: Balanced truncation model reduction for semidiscretized Stokes equation. Linear Algebra Appl. 415(2–3), 262–289 (2006). https://doi.org/10.1016/j.laa.2004.01.015
Stykel, T.: Low-rank iterative methods for projected generalized Lyapunov equations. Electron Trans Numer Anal. 30, 187–202 (2008)
Werner, S.: Hankel-norm approximation of descriptor systems. Master’s thesis, Otto-von-Guericke-Universität, Magdeburg, Germany (2016). http://nbn-resolving.de/urn:nbn:de:gbv:ma9:1-8845
Funding
Open access funding provided by Projekt DEAL. This work was supported by the German Research Foundation (DFG) Priority Program 1897: “Calm, Smooth and Smart – Novel Approaches for Influencing Vibrations by Means of Deliberately Introduced Dissipation” and the German Research Foundation (DFG) Research Training Group 2297 “MathCoRe”, Magdeburg.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: Anthony Nouy
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This article belongs to the Topical Collection: Model reduction of parametrized Systems
Guest Editors: Anthony Nouy, Peter Benner, Mario Ohlberger, Gianluigi Rozza, Karsten Urban and Karen Willcox
Appendix
Appendix
For the proof of Theorem 1, the following lemma is used.
Lemma 1
Every all-pass transfer function\(G(s) \in \mathbb {C}^{m \times m}\)is proper.
Proof
From the definition of all-pass transfer functions follows that the product G(s)GT(−s) = Im has to be proper.
Improper Case: First, we assume that G is an improper transfer function. The entries of G(s) are rational functions with real coefficients. Since G is improper, at least one entry of G must have a higher polynomial degree in the numerator than in the denominator. Also, one can observe that for GT(−s) the entries of the matrix are only transposed and coefficients of odd polynomial order change their signs. In the single-input single-output (SISO) case G(s) is given by \( G(s) = \frac {n(s)}{d(s)}\), with deg(n) > deg(d). Let the numerator and denominator of the para-Hermitian function be denoted by \({\tilde {n}}(s)\) and \({\tilde {d}}(s)\). In this case, it is obvious that for the product it holds \(2 \cdot \text {deg}(n) = \text {deg}(n{\tilde {n}}) > \text {deg}(d{\tilde {d}}) = 2 \cdot \text {deg}(d)\). So the product is always improper.
In the multi-input multi-output (MIMO) case, for simplicity, it is assumed that m = 2 and that the denominator is equal for all entries and is factored out such that
The resulting product is then
If only one of the entries of G(s) would have a higher polynomial degree than the denominator, the argumentation from the SISO case would follow. Therefore, we can assume w.l.o.g. that
For simplicity, we concentrate on the (1, 1) entry of the matrix product. For the resulting polynomial degrees it holds \(\text {deg}(n_{11}{\tilde {n}}_{11}) = 2g + 2\), \(\text {deg}(n_{12}{\tilde {n}}_{12}) = 2g + 2\), \(\text {deg}(n_{11}{\tilde {n}}_{11} + n_{12}{\tilde {n}}_{12}) \leq 2g + 2\), \(\text {deg}(d{\tilde {d}}) = 2g\). To get a proper transfer function in the product, we need that the coefficients in \(n_{11}{\tilde {n}}_{11} + n_{12}{\tilde {n}}_{12,}\) corresponding to the two highest exponents, cancel out. If we now develop the polynomials as
we get for the first coefficients \(n_{11,g+1}{\tilde {n}}_{11,g+1} = -n_{12,g+1}{\tilde {n}}_{12,g+1}\), with \(\lvert n_{11,g+1} \rvert = \lvert {\tilde {n}}_{11,g+1} \rvert \) and \(\lvert n_{12,g+1} \rvert = \lvert {\tilde {n}}_{12,g+1} \rvert \). Now, if g + 1 is even then
and if g + 1 is odd
Both cases are a contradiction to the condition that the coefficients are real and non-zero. Therefore, an all-pass transfer function cannot be improper.
Strictly Proper Case: Now, let us assume that G is a strictly proper transfer function. Using the same argumentation as in the improper case, we get that the product of a strictly proper transfer function with its para-Hermitian is also strictly proper. □
Now, we proof the results of Theorem 1.
Proof
At first, we can assume w.l.o.g. that ς = 1, since the system can be scaled to that case by \({\tilde {B}} = \varsigma ^{-\frac {1}{2}}B\), \({\tilde {C}} = \varsigma ^{-\frac {1}{2}}C\) and \({\tilde {D}} = \varsigma ^{-1}D\).“⇒”: Assume the transfer function G(s) is all-pass. From Lemma 1 it follows that G(s) has to be proper. If we consider now the decomposition of the transfer function into its strictly proper and polynomial part G(s) = Gsp(s) + P(s), the polynomial part must satisfy
with Mk = 0 for all k ≥ 1. In this case, it holds \(\lim \limits _{s \rightarrow \infty }G(s) = M_{0}\), and with the definition of all-pass transfer functions we get \(M_{0}M_{0}^{{\mkern -1.5mu\mathsf {T}}} = G(s)G^{{\mkern -1.5mu\mathsf {T}}}(-s) = I_{m}\). Therefore, the expressions (28) and (29) hold. Since the matrix pencil λE − A is assumed to be regular, there are non-singular matrices \(Q, Z \in \mathbb {R}^{n \times n}\), which resemble the Weierstrass canonical form (4), similar to (21). Using P and Q for a restricted system equivalence transformation leads to the block partitioned realization
where λEf − Af contains all the finite eigenvalues of λE − A and \(\lambda E_{\infty } - A_{\infty }\) contains only infinite eigenvalues. This block diagonal system decouples into its slow and fast subsystems (32), (33), with the realizations (Ef,Af,Bf,Cf, 0) and \((E_{\infty }, A_{\infty }, B_{\infty }, C_{\infty }, D)\). While the slow subsystem corresponds to the strictly proper part of the transfer function, the fast subsystem belongs to the polynomial part. The constant part of the transfer function is then given by \(M_{0} = D - C_{\infty }A_{\infty }^{-1}B_{\infty }\) and the transfer function can also be realized as G(s) = Cf(sEf − Af)− 1Bf + M0, with invertible matrix Ef.
By the definition of an all-pass transfer function, i.e., G(s)GT(−s) = Im, we get the equality G− 1(s) = GT(−s), which can be written as
The equality \(M_{0}^{-1} = M_{0}^{{\mkern -1.5mu\mathsf {T}}}\) was already proven above. From the R-controllability and R-observability assumption together with the regularity of Ef, it follows that there exist invertible matrices \(T, W \in \mathbb {R}^{n \times n}\), which transform one realization into the other, i.e.,
By reformulating (49) we obtain
and from (50) we get
The equation (48) can be rewritten as
and for (47) we analogously get
Therefore, T and W−T, as well as T− 1 and WT, satisfy the same set of equations, which means that W = T−T. Using this, the expressions (47)–(50) are equivalent to
Then, the matrix T is given as the solution of the system of matrix equations following from (51), (52) and (54)
Using the fact that Ef is invertible, we can define the symmetric matrix \({\tilde {G}}_{pc} = -TE_{f}^{-{\mkern -1.5mu\mathsf {T}}} = -E_{f}^{-1}T^{{\mkern -1.5mu\mathsf {T}}}\) and replace the system of matrix equations by the following generalized Lyapunov equation
For the matrix \({\tilde {G}}_{pc}\), it then holds that
Additionally, from (53) the following constraint is obtained
While observing that the dual conditions can be obtained analogously by using (51), (52) and (53), the all-pass characterization is proven for the realization of G with the invertible matrix Ef.
In the next step, the original realization of the system has to be rebuild by using the block diagonal structure (46). Therefore, we need to apply appropriate spectral projectors of the deflating subspaces corresponding to the finite eigenvalues of the matrix pencil λE − A. In case of (46), those left and right spectral projectors are given by
Since the matrices \({\tilde {G}}_{pc}\) and \({\tilde {G}}_{po}\) are only determined by the system parts corresponding to the finite eigenvalues, they have to be expanded accordingly to the spectral projectors by
Using this, the equation (55) is equivalent to
Also, the matrix product in (56) becomes
and the constraint (57) becomes
Now, this realization has to be back-transformed into the original one. By multiplying (55) from the left with Q− 1 and from the right with Q−T we get
with the spectral projection
and the symmetric matrix
Therefore, the conditions (22) and (24) are satisfied. For the condition (22), it holds
The condition (26) for the proper Hankel singular values is then
For the constraint (30), it holds
Note, that the conditions (23), (25), (23), (27) and (27) follow analogously by using the dual equations and concepts. Hence, all conditions of the characterization are fulfilled.“⇐”: Now, it is assumed that the conditions (22)–(31) hold. It has to be shown that the resulting transfer function of the linear descriptor system is all-pass. Therefore, a reformulation of (24) is considered
The right-hand side of this expression shall be transformed into the form of a transfer function and its para-Hermitian. It holds
In the parts with the symmetric matrix \(\mathcal {G}_{pc}\), there is also the additional spectral projector Pr. Following (22), we get that \(P_{r}\mathcal {G}_{pc} = \mathcal {G}_{pc}\) and it holds
Now, the additional constraint (31) leads to
and, inserting the definition of the spectral projectors, we get on the left-hand side
For the right-hand side we get
Using the above expressions, the all-pass condition is satisfied
□
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Benner, P., Werner, S.W.R. Hankel-norm approximation of large-scale descriptor systems. Adv Comput Math 46, 40 (2020). https://doi.org/10.1007/s10444-020-09750-w
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10444-020-09750-w