Abstract
In this article we investigate model order reduction of large-scale systems using time-limited balanced truncation, which restricts the well known balanced truncation framework to prescribed finite time intervals. The main emphasis is on the efficient numerical realization of this model reduction approach in case of large system dimensions. We discuss numerical methods to deal with the resulting matrix exponential functions and Lyapunov equations which are solved for low-rank approximations. Our main tool for this purpose are rational Krylov subspace methods. We also discuss the eigenvalue decay and numerical rank of the solutions of the Lyapunov equations. These results, and also numerical experiments, will show that depending on the final time horizon, the numerical rank of the Lyapunov solutions in time-limited balanced truncation can be smaller compared to standard balanced truncation. In numerical experiments we test the approaches for computing low-rank factors of the involved Lyapunov solutions and illustrate that time-limited balanced truncation can generate reduced order models having a higher accuracy in the considered time region.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Al-Mohy, A.H., Higham, N.J.: Computing the action of the matrix exponential, with an application to exponential integrators. SIAM J. Sci. Comput. 33(2), 488–511 (2011)
Antoulas, A.C., Sorensen, D.C., Zhou, Y.: On the decay rate of Hankel singular values and related issues. Syst. Cont. Lett. 46(5), 323–342 (2002)
Baker, J., Embree, M., Sabino, J.: Fast singular value decay for Lyapunov solutions with nonnormal coefficients. SIAM J. Matrix Anal. Appl. 36(2), 656–668 (2015)
Bartels, R.H., Stewart, G.W.: Solution of the matrix equation A X + X B = C: Algorithm 432. Comm. ACM 15, 820–826 (1972)
Beattie, C., Gugercin, S., Mehrmann, V.: Model reduction for systems with inhomogeneous initial conditions. Syst. Control Lett. 99, 99–106 (2017). https://doi.org/10.1016/j.sysconle.2016.11.007
Beckermann, B., Reichel, L.: Error estimates and evaluation of matrix functions via the faber transform. SIAM J. Numer. Anal. 47(5), 3849–3883 (2009). https://doi.org/10.1137/080741744
Benner, P.: Solving large-scale control problems. IEEE Control Syst. Mag. 14 (1), 44–59 (2004)
Benner, P., Kürschner, P., Saak, J.: Frequency-limited balanced truncation with low-rank approximations. SIAM J. Sci. Comput. 38(1), A471–A499 (2016). https://doi.org/10.1137/15M1030911
Benner, P., Saak, J.: Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey. GAMM Mitteilungen 36(1), 32–52 (2013). https://doi.org/10.1002/gamm.201310003
Berljafa, M., Güttel, S.: Generalized rational krylov decompositions with an application to rational approximation. SIAM J. Matrix Anal. Appl. 36(2), 894–916 (2015)
Breiten, T., Beattie, C., Gugercin, S.: Near-optimal frequency-weighted interpolatory model reduction. Sys. Control Lett. 78, 8–18 (2015)
Caliari, M., Kandolf, P., Ostermann, A., Rainer, S.: Comparison of software for computing the action of the matrix exponential. BIT 54(1), 113–128 (2014)
Davies, P.I., Higham, N.J.: Computing f(A)b for matrix functions f. In: Boriçi, A., Frommer, A., Joó, B., Kennedy, A., Pendleton, B. (eds.) QCD and Numerical Analysis III, Lect. Notes Comput. Sci. Eng. vol. 47, pp. 15–24. Springer, Berlin (2005). https://doi.org/10.1007/3-540-28504-0_2
Druskin, V., Knizhnerman, L., Zaslavsky, M.: Solution of large scale evolutionary problems using rational krylov subspaces with optimized shifts. SIAM J. Sci. Comput. 31(5), 3760–3780 (2009)
Druskin, V., Lieberman, C., Zaslavsky, M.: On adaptive choice of shifts in rational krylov subspace reduction of evolutionary problems. SIAM J. Sci. Comput. 32(5), 2485–2496 (2010)
Druskin, V., Simoncini, V.: Adaptive rational Krylov subspaces for large-scale dynamical systems. Syst. Control Lett. 60(8), 546–560 (2011)
Druskin, V., Simoncini, V., Zaslavsky, M.: Adaptive tangential interpolation in rational Krylov subspaces for MIMO dynamical systems. SIAM J. Matrix Anal. Appl. 35(2), 476–498 (2014). https://doi.org/10.1137/120898784
Du, X., Benner, P.: Finite-Frequency Model Order Reduction of Linear Systems via Parameterized Frequency-dependent Balanced Truncation. Tech. Rep. 1602.04408. ArXiv e-prints (2016)
Du, X., Benner, P., Yang, G., Ye, D.: Balanced truncation of linear time-invariant systems at a single frequency. Preprint MPIMD/13-02, Max Planck Institute Magdeburg. Available from http://www.mpi-magdeburg.mpg.de/preprints/(2013)
Ewins, D.: Modal testing: theory, practice, and application (2nd edn) Research Study Press LTD (2000)
Fehr, J., Fischer, M., Haasdonk, B., Eberhard, P.: Greedy-based approximation of frequency-weighted Gramian matrices for model reduction in multibody dynamics. Z. Angew. Math. Mech. 93(8), 501–519 (2013)
Freitas, F., Rommes, J., Martins, N.: Gramian-based reduction method applied to large sparse power system descriptor models. IEEE Trans. Power Syst. 23 (3), 1258–1270 (2008)
Frommer, A., Lund, K., Szyld, D.B.: Block Krylov subspace methods for computing functions of matrices applied to multiple vectors. Tech. Rep. 17-03-21, Department of Mathematics Temple University (2017)
Frommer, A., Simoncini, V.: Matrix functions. In: Schilders, W., van der Vorst, H., Rommes, J. (eds.) Model Order Reduction: Theory, Research Aspects and Applications, Mathematics in Industry, vol. 13, pp. 275–303. Springer, Berlin (2008). https://doi.org/10.1007/978-3-540-78841-6_13
Gawronski, W., Juang, J.: Model reduction in limited time and frequency intervals. Int. J. Syst. Sci. 21(2), 349–376 (1990). https://doi.org/10.1080/00207729008910366
Goyal, P., Redmann, M.: Towards time-limited \(\mathcal {H}_{2}\)-optimal model order reduction. Tech. Rep. WIAS Preprint No. 2441 (2017)
Grasedyck, L.: Existence of a low rank or H-matrix approximant to the solution of a Sylvester equation. Numer. Lin. Alg. Appl. 11, 371–389 (2004)
Großmann, K., Städel, C., Galant, A., Mühl, A.: Berechnung von Temperaturfeldern an Werkzeugmaschinen. Zeitschrift fü,r Wirtschaftlichen Fabrikbetrieb 107(6), 452–456 (2012)
Gugercin, S., Antoulas, A.C.: A survey of model reduction by balanced truncation and some new results. Internat. J. Control 77(8), 748–766 (2004). https://doi.org/10.1080/00207170410001713448
Güttel, S.: Rational Krylov Methods for Operator Functions. Ph.D. thesis, Technische Universität Bergakademie Freiberg, Germany. Available from http://nbn-resolving.de/urn:nbn:de:bsz:105-qucosa-27645 (2010)
Güttel, S.: Rational Krylov approximation of matrix functions: Numerical methods and optimal pole selection. GAMM-Mitteilungen 36(1), 8–31 (2013). https://doi.org/10.1002/gamm.201310002
Halevi, Y.: Frequency weighted model reduction via optimal projection. IEEE Trans. Automat. Control 37(10), 1537–1542 (1992)
Heinkenschloss, M., Reis, T., Antoulas, A.C.: Balanced truncation model reduction for systems with inhomogeneous initial conditions. Automatica 47(3), 559–564 (2011). https://doi.org/10.1016/j.automatica.2010.12.002
Higham, N.: Functions of matrices: Theory and Computation. Society for Industrial and Applied Mathematics, Philadelphia (2008)
Knizhnerman, L.A.: Calculation of functions of unsymmetric matrices using Arnoldi’s method. Comput. Math. Math. Phys. 31(1), 1–9 (1992)
Moore, B.C.: Principal component analysis in linear systems: controllability, observability, and model reduction. IEEE Trans. Autom. Control AC–26(1), 17–32 (1981). https://doi.org/10.1109/TAC.1981.1102568
Penzl, T.: Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case. Syst. Cont. Lett. 40, 139–144 (2000). https://doi.org/10.1016/S0167-6911(00)00010-4
Petersson, D.: A Nonlinear Optimization Approach to H2-Optimal Modeling and Control. Ph.D. thesis, Linköping University. Available from http://www.diva-portal.org/smash/get/diva2:647068/FULLTEXT01.pdf (2013)
Petersson, D., Löfberg, J.: Model reduction using a frequency-limited \(\mathcal {H}_{2}\)-cost. Sys. Control Lett. 67, 32–39 (2014)
Redmann, M., Kürschner, P.: An \(\mathcal {H}_{2}\)-Type Error Bound for Time-Limited Balanced Truncation. Tech. Rep. 1710.07572v1. ArXiv e-prints (2017)
Ruhe, A.: Rational Krylov sequence methods for eigenvalue computation. Linear Algebra Appl. 58, 391–405 (1984)
Ruhe, A.: The rational Krylov algorithm for nonsymmetric Eigenvalue problems. III: complex shifts for real matrices. BIT 34, 165–176 (1994)
Saad, Y.: Numerical Solution of Large Lyapunov Equation. In: Kaashoek, M.A., van Schuppen, J.H., Ran, A.C.M. (eds.) Signal Processing, Scattering, Operator Theory and Numerical Methods, pp. 503–511, Birkhäuser (1990)
Saad, Y.: Analysis of some Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 29(1), 209–228 (1992)
Sabino, J.: Solution of large-scale Lyapunov equations via the block modified smith method. Ph.D. thesis, Rice University, Houston, Texas. http://www.caam.rice.edu/tech_reports/2006/TR06-08.pdf (2007)
Simoncini, V.: Analysis of the rational Krylov subspace projection method for large-scale algebraic Riccati equations. SIAM J. Matrix Anal. Appl. 37(4), 1655–1674 (2016). https://doi.org/10.1137/16M1059382
Sinani, K., Gugercin, S.: Iterative Rational Krylov Algorithms for Unstable Dynamical Systems and Optimality Conditions for a Finite-Time Horizon (2017). http://meetings.siam.org/sess/dsp_talk.cfm?p=81168 SIAM CSE (2017)
Truhar, N., Veselić, K.: Bounds on the trace of a solution to the Lyapunov equation with a general stable matrix. Syst. Cont. Lett. 56(7–8), 493–503 (2007). https://doi.org/10.1016/j.sysconle.2007.02.003
Vuillemin, P.: Frequency-limited model approximation of large-scale dynamical models. Ph.D. thesis, Université de Toulouse. https://hal.archives-ouvertes.fr/tel-01092051 (2014)
Acknowledgments
Open access funding provided by Max Planck Society. I thank the referees for their helpful comments. Moreover, I am grateful for the constructive discussions with Maria Cruz Varona, Serkan Gugercin, and Stefan Guettel.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: Peter Benner
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Kürschner, P. Balanced truncation model order reduction in limited time intervals for large systems. Adv Comput Math 44, 1821–1844 (2018). https://doi.org/10.1007/s10444-018-9608-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10444-018-9608-6
Keywords
- Lyapunov equation
- Rational Krylov subspaces
- Model order reduction
- Balanced truncation
- Matrix exponential