Matrix equations, sparse solvers: M-M.E.S.S.-2.0.1 – philosophy, features, and application for (parametric) model order reduction. (English) Zbl 1480.93048
Benner, Peter (ed.) et al., Model reduction of complex dynamical systems. Selected papers based on the presentations at the workshop, University of Graz, Graz, Austria, August 28–30, 2019. Cham: Birkhäuser. ISNM, Int. Ser. Numer. Math. 171, 369-392 (2021).
Summary: Matrix equations are omnipresent in (numerical) linear algebra and systems theory. Especially in model order reduction (MOR), they play a key role in many balancing-based reduction methods for linear dynamical systems. When these systems arise from spatial discretizations of evolutionary partial differential equations, their coefficient matrices are typically large and sparse. Moreover, the numbers of inputs and outputs of these systems are typically far smaller than the number of spatial degrees of freedom. Then, in many situations, the solutions of the corresponding large-scale matrix equations are observed to have low (numerical) rank. This feature is exploited by M-M.E.S.S. to find successively larger low-rank factorizations approximating the solutions. This contribution describes the basic philosophy behind the implementation and the features of the package, as well as its application in the MOR of large-scale linear time-invariant (LTI) systems and parametric LTI systems.
For the entire collection see [Zbl 1470.93005].
For the entire collection see [Zbl 1470.93005].
MSC:
| 93B11 | System structure simplification |
| 93B25 | Algebraic methods |
| 93C05 | Linear systems in control theory |
| 93-04 | Software, source code, etc. for problems pertaining to systems and control theory |
References:
| [1] | Jbilou, K., Messaoudi, A.: A computational method for symmetric Stein matrix equations. In: Van Dooren, P., Bhattacharyya, S.P., Chan, R.H., Olshevsky, V., Routray, A. (eds.) Numerical Linear Algebra in Signals, Systems and Control. Lecture Notes in Electrical Engineering, vol. 80. Springer, New York (2011). https://doi.org/10.1007/978-94-007-0602-6_14 · Zbl 1251.65059 |
| [2] | Driscoll, T.A., Hale, N., Trefethen, L.N.: Chebfun Guide. Pafnuty Publications (2014). http://www.chebfun.org/docs/guide/ |
| [3] | Benner, P., Goyal, P.: Balanced truncation model order reduction for quadratic-bilinear systems (2017). arXiv preprint arXiv:1705.00160 [math.OC] |
| [4] | Amsallem, D., Farhat, C.: An online method for interpolating linear parametric reduced-order models. SIAM J. Sci. Comput. 33(5), 2169-2198 (2011). https://doi.org/10.1137/100813051 · Zbl 1269.65059 · doi:10.1137/100813051 |
| [5] | Antoulas, A.C.: Approximation of Large-Scale Dynamical Systems, Advances in Design and Control, vol. 6. SIAM Publications, Philadelphia (2005). https://doi.org/10.1137/1.9780898718713 · Zbl 1112.93002 |
| [6] | Batten King, B., Hovakimyan, N., Evans, K.A., Buhl, M.: Reduced order controllers for distributed parameter systems: LQG balanced truncation and an adaptive approach. Math. Comput. Model. 43(9), 1136-1149 (2006). https://doi.org/10.1016/j.mcm.2005.05.031 · Zbl 1136.93344 · doi:10.1016/j.mcm.2005.05.031 |
| [7] | Baur, U., Beattie, C.A., Benner, P., Gugercin, S.: Interpolatory projection methods for parameterized model reduction. SIAM J. Sci. Comput. 33(5), 2489-2518 (2011). https://doi.org/10.1137/090776925 · Zbl 1254.93032 · doi:10.1137/090776925 |
| [8] | Bendixson, I.: Sur les racines d’une équation fondamentale. Acta Math. 25(1), 359-365 (1902). https://doi.org/10.1007/BF02419030 · JFM 33.0106.01 · doi:10.1007/BF02419030 |
| [9] | Benner, P., Bujanović, Z., Kürschner, P., Saak, J.: RADI: a low-rank ADI-type algorithm for large scale algebraic Riccati equations. Numer. Math. 138(2), 301-330 (2018). https://doi.org/10.1007/s00211-017-0907-5 · Zbl 1385.65035 · doi:10.1007/s00211-017-0907-5 |
| [10] | Benner, P., Grundel, S., Hornung, N.: Parametric model order reduction with a small \({\cal{H}}_2\)-error using radial basis functions. Adv. Comput. Math. 41(5), 1231-1253 (2015). https://doi.org/10.1007/s10444-015-9410-7 · Zbl 1348.65096 · doi:10.1007/s10444-015-9410-7 |
| [11] | Benner, P., Gugercin, S., Willcox, K.: A survey of model reduction methods for parametric systems. SIAM Rev. 57(4), 483-531 (2015). https://doi.org/10.1137/130932715 · Zbl 1339.37089 · doi:10.1137/130932715 |
| [12] | Benner, P., Heiland, J.: LQG-balanced truncation low-order controller for stabilization of laminar flows. In: King, R. (ed.) Active Flow and Combustion Control 2014. Notes on Numerical Fluid Mechanics and Multidisciplinary Design, vol. 127, pp. 365-379. Springer International Publishing (2015). https://doi.org/10.1007/978-3-319-11967-0_22 · Zbl 1308.76105 |
| [13] | Benner, P., Kürschner, P.: Computing real low-rank solutions of Sylvester equations by the factored ADI method. Comput. Math. Appl. 67(9), 1656-1672 (2014). https://doi.org/10.1016/j.camwa.2014.03.004 · Zbl 1364.65093 · doi:10.1016/j.camwa.2014.03.004 |
| [14] | Benner, P., Kürschner, P., Saak, J.: Low-rank Newton-ADI methods for large nonsymmetric algebraic Riccati equations. J. Frankl. Inst. 353(5), 1147-1167 (2016). https://doi.org/10.1016/j.jfranklin.2015.04.016 · Zbl 1336.93056 · doi:10.1016/j.jfranklin.2015.04.016 |
| [15] | Benner, P., Li, J.R., Penzl, T.: Numerical solution of large-scale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems. Numer. Linear Algebr. Appl. 15(9), 755-777 (2008). https://doi.org/10.1002/nla.622 · Zbl 1212.65245 · doi:10.1002/nla.622 |
| [16] | Benner, P., Saak, J.: A semi-discretized heat transfer model for optimal cooling of steel profiles. In: Benner, P., Mehrmann, V., Sorensen, D. (eds.) Dimension Reduction of Large-Scale Systems. Lecture Notes in Computational Science and Engineering, vol. 45, pp. 353-356. Springer, Berlin/Heidelberg (2005). https://doi.org/10.1007/3-540-27909-1_19 · Zbl 1170.80341 |
| [17] | Benner, P., Saak, J., Schieweck, F., Skrzypacz, P., Weichelt, H.K.: A non-conforming composite quadrilateral finite element pair for feedback stabilization of the Stokes equations. J. Numer. Math. 22(3), 191-220 (2014). https://doi.org/10.1515/jnma-2014-0009 · Zbl 1303.65095 · doi:10.1515/jnma-2014-0009 |
| [18] | Benner, P., Werner, S.W.R.: MORLAB - the Model Order Reduction LABoratory (2020). arXiv preprint arXiv: 2002.12682 [Cs.MS]. https://doi.org/10.1007/978-3-030-72983-7_19 |
| [19] | Breiten, T.: Interpolatory methods for model reduction of large-scale dynamical systems. Dissertation, Department of Mathematics, Otto-von-Guericke University, Magdeburg, Germany (2013). https://doi.org/10.25673/3917 · Zbl 1283.93003 |
| [20] | Castagnotto, A., Cruz Varona, M., Jeschek, L., Lohmann, B.: sss & sssMOR: analysis and reduction of large-scale dynamic systems in MATLAB. at-Automatisierungstechnik 65(2), 134-150 (2017). https://doi.org/10.1515/auto-2016-0137 |
| [21] | Fehr, J., Grunert, D., Holzwarth, P., Fröhlich, B., Walker, N., Eberhard, P.: Morembs—a model order reduction package for elastic multibody systems and beyond. In: Reduced-Order Modeling (ROM) for Simulation and Optimization: Powerful Algorithms as Key Enablers for Scientific Computing, pp. 141-166. Springer International Publishing, Cham (2018). https://doi.org/10.1007/978-3-319-75319-5_7 · Zbl 1433.74004 |
| [22] | 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). https://doi.org/10.1109/TPWRS.2008.926693 · doi:10.1109/TPWRS.2008.926693 |
| [23] | Geuß, M., Butnaru, D., Peherstorfer, B., Bungartz, H., Lohmann, B.: Parametric model order reduction by sparse-grid-based interpolation on matrix manifolds for multidimensional parameter spaces. In: Proceedings of the European Control Conference, Strasbourg, France, pp. 2727-2732 (2014). https://doi.org/10.1109/ECC.2014.6862414 |
| [24] | Geuß, M., Panzer, H., Wirtz, A., Lohmann, B.: A general framework for parametric model order reduction by matrix interpolation. In: Workshop on Model Reduction of Parametrized Systems II (MoRePaS II) (2012) |
| [25] | Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2013) · Zbl 1268.65037 |
| [26] | Gugercin, S., Antoulas, A.C., Beattie, C.: \( \cal{H}_2\) model reduction for large-scale linear dynamical systems. SIAM J. Matrix Anal. Appl. 30(2), 609-638 (2008). https://doi.org/10.1137/060666123 · Zbl 1159.93318 · doi:10.1137/060666123 |
| [27] | Gugercin, S., Li, J.R.: Smith-type methods for balanced truncation of large systems. In: Benner, P., Mehrmann, V., Sorensen, D. (eds.) Dimension Reduction of Large-Scale Systems. Lecture Notes in Computational Science and Engineering, vol. 45, pp. 49-82. Springer, Berlin/Heidelberg (2005) · Zbl 1215.93026 |
| [28] | Heinkenschloss, M., Sorensen, D.C., Sun, K.: Balanced truncation model reduction for a class of descriptor systems with application to the Oseen equations. SIAM J. Sci. Comput. 30(2), 1038-1063 (2008). https://doi.org/10.1137/070681910 · Zbl 1216.76015 · doi:10.1137/070681910 |
| [29] | Himpe, C.: Comparing (empirical-Gramian-based) model order reduction algorithms (2020). arXiv preprint arXiv:2002.12226 [math.OC]. https://doi.org/10.1007/978-3-030-72983-7_7 |
| [30] | Kleinman, D.L.: On an iterative technique for Riccati equation computations. IEEE Trans. Autom. Control 13(1), 114-115 (1968). https://doi.org/10.1109/TAC.1968.1098829 · doi:10.1109/TAC.1968.1098829 |
| [31] | Kürschner, P.: Efficient low-rank solution of large-scale matrix equations. Dissertation, Otto-von-Guericke-Universität, Magdeburg, Germany (2016). http://hdl.handle.net/11858/00-001M-0000-0029-CE18-2. Shaker Verlag, ISBN 978-3-8440-4385-3 |
| [32] | Lang, N.: Numerical methods for large-scale linear time-varying control systems and related differential matrix equations. Dissertation, Technische Universität Chemnitz, Germany (2017). https://www.logos-verlag.de/cgi-bin/buch/isbn/4700. Logos-Verlag, Berlin, ISBN 978-3-8325-4700-4 |
| [33] | Lanzon, A., Feng, Y., Anderson, B.D.O.: An iterative algorithm to solve algebraic Riccati equations with an indefinite quadratic term. In: 2007 European Control Conference (ECC), pp. 3033-3039 (2007). https://doi.org/10.23919/ecc.2007.7068239 |
| [34] | Laub, A.J., Heath, M.T., Paige, C.C., Ward, R.C.: Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms. IEEE Trans. Autom. Control 32(2), 115-122 (1987). https://doi.org/10.1109/TAC.1987.1104549 · Zbl 0624.93025 · doi:10.1109/TAC.1987.1104549 |
| [35] | Li, T., Weng, P.C.Y., Chu, E.K.w., Lin, W.W.: Large-scale Stein and Lyapunov equations, Smith method, and applications. Numer. Algorithms 63(4), 727-752 (2013). https://doi.org/10.1007/s11075-012-9650-2 · Zbl 1271.65079 |
| [36] | Lin, Y., Simoncini, V.: A new subspace iteration method for the algebraic Riccati equation. Numer. Linear Algebr. Appl. 22(1), 26-47 (2015). https://doi.org/10.1002/nla.1936 · Zbl 1363.65076 · doi:10.1002/nla.1936 |
| [37] | Möckel, J., Reis, T., Stykel, T.: Linear-quadratic Gaussian balancing for model reduction of differential-algebraic systems. Int. J. Control 84(10), 1627-1643 (2011). https://doi.org/10.1080/00207179.2011.622791 · Zbl 1236.93036 · doi:10.1080/00207179.2011.622791 |
| [38] | 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 · Zbl 0464.93022 |
| [39] | MORPACK (model order reduction package). https://tu-dresden.de/ing/maschinenwesen/ifkm/dmt/forschung/projekte/morpack |
| [40] | Mustafa, D., Glover, K.: Controller reduction by \(\cal{H}_\infty \)-balanced truncation. IEEE Trans. Autom. Control 36(6), 668-682 (1991). https://doi.org/10.1109/9.86941 · doi:10.1109/9.86941 |
| [41] | Oberwolfach Benchmark Collection: Steel profile. hosted at MORwiki - Model Order Reduction Wiki (2005). http://modelreduction.org/index.php/Steel_Profile |
| [42] | Panzer, H., Mohring, J., Eid, R., Lohmann, B.: Parametric model order reduction by matrix interpolation. at-Automatisierungstechnik 58(8), 475-484 (2010) |
| [43] | Penzl, T.: A cyclic low rank Smith method for large sparse Lyapunov equations. SIAM J. Sci. Comput. 21(4), 1401-1418 (2000). https://doi.org/10.1137/S1064827598347666 · Zbl 0958.65052 · doi:10.1137/S1064827598347666 |
| [44] | Penzl, T.: Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case. Syst. Control Lett. 40, 139-144 (2000). https://doi.org/10.1016/S0167-6911(00)00010-4 · Zbl 0977.93034 · doi:10.1016/S0167-6911(00)00010-4 |
| [45] | Penzl, T.: Lyapack users guide. Technical Report SFB393/00-33, Sonderforschungsbereich 393, Numerische Simulation auf massiv parallelen Rechnern, TU Chemnitz, 09107 Chemnitz, Germany (2000). Available at http://www.tu-chemnitz.de/sfb393/sfb00pr.html |
| [46] | Poloni, F., Reis, T.: A deflation approach for large-scale Lur’e equations. SIAM J. Matrix Anal. Appl. 33(4), 1339-1368 (2012). https://doi.org/10.1137/120861679 · Zbl 1263.15015 · doi:10.1137/120861679 |
| [47] | Pontes Duff, I., Kürschner, P.: Numerical computation and new output bounds for time-limited balanced truncation of discrete-time systems. Linear Algebra Appl. 623, 367-397. https://doi.org/10.1016/j.laa.2020.09.029 (2019). arXiv preprint arXiv:1902.01652 [math.NA] · Zbl 1469.93010 |
| [48] | Reis, T., Stykel, T.: Balanced truncation model reduction of second-order systems. Math. Comput. Model. Dyn. Syst. 14(5), 391-406 (2008). https://doi.org/10.1080/13873950701844170 · Zbl 1151.93010 · doi:10.1080/13873950701844170 |
| [49] | Simoncini, V., Druskin, V.: Convergence analysis of projection methods for the numerical solution of large Lyapunov equations. SIAM J. Numer. Anal. 47(2), 828-843 (2009). https://doi.org/10.1137/070699378 · Zbl 1195.65058 · doi:10.1137/070699378 |
| [50] | Simoncini, V., Szyld, D.B., Monsalve, M.: On two numerical methods for the solution of large-scale algebraic Riccati equations. IMA J. Numer. Anal. 34(3), 904-920 (2014). https://doi.org/10.1093/imanum/drt015 · Zbl 1298.65083 · doi:10.1093/imanum/drt015 |
| [51] | Stillfjord, T.: Low-rank second-order splitting of large-scale differential Riccati equations. IEEE Trans. Autom. Control 60(10), 2791-2796 (2015). https://doi.org/10.1109/TAC.2015.2398889 · Zbl 1360.65192 · doi:10.1109/TAC.2015.2398889 |
| [52] | Stillfjord, T.: Adaptive high-order splitting schemes for large-scale differential Riccati equations. Numer. Algorithms 78, 1129-1151 (2018). https://doi.org/10.1007/s11075-017-0416-8 · Zbl 1404.65060 · doi:10.1007/s11075-017-0416-8 |
| [53] | Truhar, N., Veselić, K.: An efficient method for estimating the optimal dampers’ viscosity for linear vibrating systems using Lyapunov equation. SIAM J. Matrix Anal. Appl. 31(1), 18-39 (2009). https://doi.org/10.1137/070683052 · Zbl 1303.70021 · doi:10.1137/070683052 |
| [54] | Uddin, M.M.: Computational methods for model reduction of large-scale sparse structured descriptor systems. Dissertation, Department of Mathematics, Otto-von-Guericke University, Magdeburg, Germany (2015). http://nbn-resolving.de/urn:nbn:de:gbv:ma9:1-6535 |
| [55] | Yue, Y., Feng, L., Benner, P.: An adaptive pole-matching method for interpolating reduced-order models (2019). arXiv preprint arXiv:1908.00820 [math |
| [56] | Uddin, M.M.: Computational Methods for Approximation of Large-Scale Dynamical Systems. CRC Press, Boca Raton (2019). https://doi.org/10.1201/9781351028622 · Zbl 1416.65005 |
| [57] | Weichelt, H.K.: Numerical aspects of flow stabilization by Riccati feedback. Dissertation, Otto-von-Guericke-Universität, Magdeburg, Germany (2016). http://nbn-resolving.de/urn:nbn:de:gbv:ma9:1-8693 |
| [58] | Tombs, M.S., Postlethwaite, I.: Truncated balanced realization of a stable non-minimal state-space system. Int. J. Control 46(4), 1319-1330 (1987). https://doi.org/10.1080/00207178708933971 · Zbl 0642.93015 · doi:10.1080/00207178708933971 |
| [59] | Rave, S., Saak, J.: A non-stationary thermal-block benchmark model for parametric model order reduction (2020). arXiv preprint arXiv:2003.00846 [math.NA]. https://doi.org/10.1007/978-3-030-72983-7_16 |
| [60] | Mlinarić, P., Rave, S., Saak, J.: Parametric model order reduction using pyMOR (2020). arXiv preprint arXiv:2003.05825 [Cs.MS]. https://doi.org/10.1007/978-3-030-72983-7_17 |
| [61] | Chebfun Developers: Chebfun — numerical computing with functions. https://www.chebfun.org/ |
| [62] | Baur, U., Benner, P.: Modellreduktion für parametrisierte Systeme durch balanciertes Abschneiden und Interpolation (Model reduction for parametric systems using balanced truncation and interpolation). at-Automatisierungstechnik 57(8), 411-420 (2009). https://doi.org/10.1524/auto.2009.0787 |
| [63] | Benner, P., Saak, J., Uddin, M.M.: Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numer. Algebr. Control Optim. 6(1), 1-20 (2016). https://doi.org/10.3934/naco.2016.6.1 · Zbl 1330.93084 · doi:10.3934/naco.2016.6.1 |
| [64] | Saak, J.: Efficient numerical solution of large scale algebraic matrix equations in PDE control and model order reduction. Dissertation, Technische Universität Chemnitz, Chemnitz, Germany (2009). http://nbn-resolving.de/urn:nbn:de:bsz:ch1-200901642 |
| [65] | Saak, J., Köhler, M., Benner, P.: M-M.E.S.S. - the matrix equations sparse solvers library. https://doi.org/10.5281/zenodo.632897. See also: https://www.mpi-magdeburg.mpg.de/projects/mess |
| [66] | Saak, J., Voigt, M.: Model reduction of constrained mechanical systems in M-M.E.S.S. IFAC-PapersOnLine 9th Vienna International Conference on Mathematical Modelling MATHMOD 2018, Vienna, Austria, 21-23 Feb 2018 51(2), 661-666 (2018). https://doi.org/10.1016/j.ifacol.2018.03.112 |
| [67] | 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, Berlin (2007). https://doi.org/10.14279/depositonce-1600 |
| [68] | Shank, S.D., Simoncini, V., Szyld, D.B.: Efficient low-rank solution of generalized Lyapunov equations. Numer. Math. 134, 327-342 (2016). https://doi.org/10.1007/s00211-015-0777-7 · Zbl 1348.65078 · doi:10.1007/s00211-015-0777-7 |
| [69] | Simoncini, V.: A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput. 29(3), 1268-1288 (2007). https://doi.org/10.1137/06066120X · Zbl 1146.65038 · doi:10.1137/06066120X |
| [70] | 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 · Zbl 06655499 · doi:10.1137/16M1059382 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
