×

Large-scale computation of \(\mathcal{L}_\infty\)-norms by a greedy subspace method. (English) Zbl 1379.65020

Summary: We are concerned with the computation of the \(\mathcal{L}_\infty\)-norm for an \(\mathcal{L}_\infty\)-function of the form \(H(s) = C(s) D(s)^{-1} B(s)\), where the middle factor is the inverse of a meromorphic matrix-valued function, and \(C(s),\, B(s)\) are meromorphic functions mapping to short-and-fat and tall-and-skinny matrices, respectively. For instance, transfer functions of descriptor systems and delay systems fall into this family. We focus on the case where the middle factor is large scale. We propose a subspace projection method to obtain approximations of the function \(H\) where the middle factor is of much smaller dimension. The \(\mathcal{L}_\infty\)-norms are computed for the resulting reduced functions, then the subspaces are refined by means of the optimal points on the imaginary axis where the \(\mathcal{L}_\infty\)-norm of the reduced function is attained. The subspace method is designed so that certain Hermite interpolation properties hold between the largest singular values of the original and reduced functions. This leads to a locally superlinearly convergent algorithm with respect to the subspace dimension, which we prove and illustrate on various numerical examples.

MSC:

65F30 Other matrix algorithms (MSC2010)
65F60 Numerical computation of matrix exponential and similar matrix functions
15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory
65D05 Numerical interpolation
65E05 General theory of numerical methods in complex analysis (potential theory, etc.)

References:

[1] U. Baur, P. Benner, and L. Feng, {\it Model order reduction for linear and nonlinear systems: A system-theoretic perspective}, Arch. Comput. Methods Eng., 21 (2014), pp. 331-358, . · Zbl 1348.93075
[2] C. Beattie and S. Gugercin, {\it Interpolatory projection methods for structure-preserving model reduction}, Systems Control Lett., 58 (2009), pp. 225-232, . · Zbl 1159.93317
[3] P. Benner, V. Sima, and M. Voigt, {\it \(\mathcal{L}_∞\)-norm computation for continuous-time descriptor systems using structured matrix pencils}, IEEE Trans. Automat. Control, 57 (2012), pp. 233-238. · Zbl 1369.93174
[4] P. Benner and M. Voigt, {\it A structured pseudospectral method for \(\mathcal{H}_∞\)-norm computation of large-scale descriptor systems}, Math. Control Signals Systems, 26 (2014), pp. 303-338. · Zbl 1290.93083
[5] S. Boyd and V. Balakrishnan, {\it A regularity result for the singular values of a transfer matrix and a quadratically convergent algorithm for computing its \({L}_∞\)-norm}, Systems Control Lett., 15 (1990), pp. 1-7. · Zbl 0704.93014
[6] N. A. Bruinsma and M. Steinbuch, {\it A fast algorithm to compute the \({H}_∞\)-norm of a transfer function matrix}, Systems Control Lett., 14 (1990), pp. 287-293. · Zbl 0699.93021
[7] A. Bunse-Gerstner, R. Byers, V. Mehrmann, and N. K. Nichols, {\it Numerical computation of an analytic singular value decomposition of a matrix valued function}, Numer. Math., 60 (1991), pp. 1-39. · Zbl 0743.65035
[8] J. V. Burke, D. Henrion, A. S. Lewis, and M. L. Overton, {\it HIFOO – A MATLAB package for fixed-order controller design and \(H_∞\) optimization}, in Proceedings of the 5th IFAC Symposium on Robust Control Design, Toulouse, France, Curran, Red Hook, NY, 2006, pp. 339-344.
[9] R. Byers, {\it A bisection method for measuring the distance of a stable matrix to the unstable matrices}, SIAM J. Sci. Stat. Comput., 9 (1988), pp. 875-881. · Zbl 0658.65044
[10] Y. Chahlaoui and P. Van Dooren, {\it A Collection of Benchmark Examples for Model Reduction of Linear Time Invariant Dynamical Systems}, Technical report, SLICOT Working Note 2002-2, 2002. · Zbl 1100.93006
[11] C. De Villemagne and R. E. Skelton, {\it Model reduction using a projection formulation}, Internat. J. Control., 40 (1987), pp. 2141-2169.
[12] N. H. Du, V. H. Linh, V. Mehrmann, and D. D. Thuan, {\it Stability and robust stability of linear time-invariant delay differential-algebraic equations}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1631-1654. · Zbl 1326.34117
[13] L. Feng and P. Benner, {\it Model order reduction for systems with non-rational transfer function arising in computational electromagnetics}, in Scientific Computing in Electrical Engineering SCEE 2008, J. Roos and L. R. J. Costa, eds., Math. Ind. 14, Springer, Berlin, 2010, pp. 512-522.
[14] M. A. Freitag, A. Spence, and P. Van Dooren, {\it Calculating the \({H}_∞\)-norm using the implicit determinant method}, Linear Algebra Appl., 35 (2014), pp. 619-635. · Zbl 1305.65161
[15] F. Freitas, J. Rommes, and N. Martins, {\it Gramian-based reduction method applied to large sparse power system descriptor models}, IEEE Trans. Power Syst., 23 (2008), pp. 1258-1270.
[16] S. Gugercin, T. Stykel, and S. Wyatt, {\it Model reduction of descriptor systems by interpolatory projection methods}, SIAM J. Sci. Comput., 35 (2013), pp. B1010-B1033. · Zbl 1290.41001
[17] N. Guglielmi, M. Gürbüzbalaban, and M. L. Overton, {\it Fast approximation of the \({H}_∞\)-norm via optimization over spectral value sets}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 709-737. · Zbl 1271.93057
[18] S. Gumussoy and W. Michiels, {\it Computing \(\mathcal{H}_∞\) norms of time-delay systems}, in Proceedings of the Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference, Shanghai, China, IEEE, Piscataway, NJ, 2009, pp. 263-268.
[19] S. Gumussoy and W. Michiels, {\it Computation of extremum singular values and the strong H-infinity norm of SISO time-delay systems}, Automatica J. IFAC, 54 (2015), pp. 266-271. · Zbl 1318.93037
[20] B. Haasdonk, {\it Reduced Basis Methods for Parametrized PDEs–A Tutorial Introduction for Stationary and Instationary Problems}, in Model Reduction and Approximation: Theory and Algorithms, Comput. Sci. Eng., P. Benner, A. Cohen, M. Ohlberger, and K. Willcox, eds., SIAM, Philadelphia, 2017, pp. 65-136. · Zbl 1378.65010
[21] D. Hinrichsen and A. J. Pritchard, {\it Stability radii of linear systems}, Systems Control Lett., 7 (1986), pp. 1-10. · Zbl 0631.93064
[22] D. Hinrichsen and A. J. Pritchard, {\it Stability radius for structured perturbations and the algebraic Riccati equation}, Systems Control Lett., 8 (1986), pp. 105-113. · Zbl 0626.93054
[23] R. A. Horn and C. R. Johnson, {\it Matrix Analysis}, Cambridge University Press, Cambridge, 1985. · Zbl 0576.15001
[24] F. Kangal, K. Meerbergen, E. Mengi, and W. Michiels, {\it A subspace method for large scale eigenvalue optimization}, SIAM J. Matrix Anal. Appl., to appear. · Zbl 1378.65090
[25] M. Karow, {\it Geometry of Spectral Value Sets}, dissertation, Universität Bremen, Bremen, Germany, 2003.
[26] P. Lancaster, {\it On eigenvalues of matrices dependent on a parameter}, Numer. Math., 6 (1964), pp. 377-387. · Zbl 0133.26201
[27] N. Martins, P. C. Pellanda, and J. Rommes, {\it Computation of transfer function dominant zeros with applications to oscillation damping control of large power systems}, IEEE Trans. Power Syst., 22 (2007), pp. 1657-1664.
[28] E. Mengi, E. A. Yildirim, and M. Kiliç, {\it Numerical optimization of eigenvalues of Hermitian matrix functions}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 699-724, . · Zbl 1307.65043
[29] T. Mitchell and M. L. Overton, {\it Fixed low-order controller design and \(H_∞\) optimization for large-scale dynamical systems}, in Proceedings of the 8th IFAC Symposium on Robust Control Design, Bratislava, Slovakia, Elsevier, 2015, pp. 25-30.
[30] T. Mitchell and M. L. Overton, {\it Hybrid expansion-contraction: A robust scaleable method for approximating the \(H_∞\) norm}, IMA J. Numer. Anal., 36 (2016), pp. 985-1014. · Zbl 1433.93100
[31] F. Rellich, {\it Perturbation Theory of Eigenvalue Problems}, Notes Math. Appl., Gordon and Breach, New York, 1969. · Zbl 0181.42002
[32] J. Rommes and N. Martins, {\it Efficient computation of multivariate transfer function dominant poles using subspace acceleration}, IEEE Trans. Power Syst., 21 (2006), pp. 1471-1483.
[33] L. N. Trefethen and M. Embree, {\it Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators}, Princeton University Press, Princeton, NJ, 2005. · Zbl 1085.15009
[34] M. Voigt, {\it On Linear-Quadratic Optimal Control and Robustness of Differential-Algebraic Systems}, Logos, Berlin, 2015. · Zbl 1329.49001
[35] A. Yousuff, D. A. Wagie, and R. E. Skelton, {\it Linear system approximation via covariance equivalent realizations}, J. Math. Anal. Appl., 106 (1985), pp. 91-115. · Zbl 0573.93073
[36] K. Zhou, J. C. Doyle, and K. Glover, {\it Robust and Optimal Control}, Prentice-Hall, Englewood Cliffs, NJ, 1996. · Zbl 0999.49500
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.