×

The Sylvester equation and approximate balanced reduction. (English) Zbl 1023.93012

Let \(\dot x(t)=Ax(t)+ Bu(t)\), \(y(t)=Cx(t) +Dy(t)\) be a linear time-invariant system, where \(A,B,C\), and \(D\) are real matrices of appropriate sizes. Assuming the system is reachable, observable, and stable (i.e., \(A\) has all its eigenvalues in the open left half-plane), the linear matrix equation \[ \left[ \begin{matrix} A & 0\\ 0 & A^T\end{matrix} \right] \left[ \begin{matrix} P & X\\ X^T & Q \end{matrix}\right] +\left[ \begin{matrix} P & X\\ X^T & Q\end{matrix} \right] \left[ \begin{matrix} A & 0\\ 0&A^T \end{matrix} \right] +\left[ \begin{matrix} B\\ C^T\end{matrix} \right] [B^TC]=0 \] has a unique solution, where \(P\), the reachability gramian, and \(Q\), the observability gramian, are positive definite. The matrix \(X\) is called the cross gramian. A part of the paper contains useful tutorial information on the gramians, their properties, especially as applied to balanced realizations, Sylvester equations, and connections with Löwner matrices and rational interpolation. Error bounds in the \(H^2\) norm are derived for truncated systems in terms of the gramians. An implicitly restarting algorithm is described to achieve approximate balancing through low rank approximation of the cross gramian. The main results are formulated for SISO systems and for symmetric MIMO systems, i.e., such that all Markov parameters \(CA^kB\), \(k=0,1,\dots\), are symmetric matrices. To deal with non-symmetric MIMO systems, an embedding into a symmetric MIMO system is proposed. Experimental results implemented via Matlab codes and described in the paper suggest that both singular values and eigenvalues of the cross gramian typically decay very rapidly, thus making it possible to approximate well the cross gramian by matrices of very low rank.

MSC:

93B11 System structure simplification
15A24 Matrix equations and identities
93B20 Minimal systems representations
41A05 Interpolation in approximation theory

Software:

IRAM; ARPACK; eigs; JDQZ; Matlab
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.C. Antoulas, Lectures on the approximation of large-scale dynamical systems, SIAM, Philadelphia, PA, 2002; A.C. Antoulas, Lectures on the approximation of large-scale dynamical systems, SIAM, Philadelphia, PA, 2002
[2] Antoulas, A. C.; Sorensen, D. C., Lyapunov, Lanczos, and inertia, Linear Algebra Appl., 326, 137-150 (2001) · Zbl 0997.65065
[3] Antoulas, A. C.; Sorensen, D. C.; Gugercin, S., A survey of model reduction methods for large-scale systems, Contemp. Math., 280, 193-219 (2001) · Zbl 1048.93014
[4] A.C. Antoulas, D.C. Sorensen, Y. Zhou, On the decay rate of the Hankel singular values and related issues, Systems and Control Letters, 2002, to appear; A.C. Antoulas, D.C. Sorensen, Y. Zhou, On the decay rate of the Hankel singular values and related issues, Systems and Control Letters, 2002, to appear · Zbl 1003.93024
[5] Antoulas, A. C.; Anderson, B. D.O., State-space and polynomial approaches to rational interpolation, (Kaashoek, M. A.; van Schuppen, J. H.; Ran, A. C.M., Realization and Modelling in System Theory. Realization and Modelling in System Theory, Proc. MTNS-89, vol. I (1990)), 73-81 · Zbl 0726.93015
[6] Anderson, B. D.O.; Antoulas, A. C., Rational interpolation and state-variable realizations, (in: Matrix Problems (Special Issue). in: Matrix Problems (Special Issue), Linear Algebra and its Applications, vol. 137/138 (1990)), 479-509 · Zbl 0715.93019
[7] Antoulas, A. C.; Anderson, B. D.O., On the scalar rational interpolation problem, (Hinrichsen, D.; Willems, J. C., Parametrization Problems (Special Issue). Parametrization Problems (Special Issue), IMA Journal of Mathematical Control and Information, vol. 3 (1986)), 61-88 · Zbl 0637.93014
[8] Boley, D. L., Krylov space methods on state-space control models, Circuits Systems Signal Process., 13, 733-758 (1994) · Zbl 0833.93024
[9] D.F. Enns, Model reduction with balanced realizations: an error bound and frequency weighted generalization, in: Proceedings of the IEEE Conference on Decision and Control, pp. 127-132, 1984; D.F. Enns, Model reduction with balanced realizations: an error bound and frequency weighted generalization, in: Proceedings of the IEEE Conference on Decision and Control, pp. 127-132, 1984
[10] Feldman, P.; Freund, R. W., Efficient linear circuit analysis by Padé approximation via a Lanczos method, IEEE Trans. Computer-Aided Design, 14, 639-649 (1995)
[11] Fernando, K. V.; Nicholson, H., On the structure of balanced and other principal representations of SISO systems, IEEE Trans. Automatic Control, AC-28, 228-231 (1983) · Zbl 0507.93021
[12] Gragg, W. B.; Lindquist, A., On the partial realization problem, (in: Linear Systems and Control (Special Issue). in: Linear Systems and Control (Special Issue), Linear Algebra and its Applications, vol. 50 (1983)), 277-319 · Zbl 0519.93024
[13] A. Greenbaum, Using the Cauchy integral formula and partial fractions decomposition of the resolvent to estimate ∥\(fA\); A. Greenbaum, Using the Cauchy integral formula and partial fractions decomposition of the resolvent to estimate ∥\(fA\)
[14] E.J. Grimme, Krylov projection methods for model reduction, Ph.D. Thesis, ECE Department, University of Illinois, Urbana-Champaign, 1997; E.J. Grimme, Krylov projection methods for model reduction, Ph.D. Thesis, ECE Department, University of Illinois, Urbana-Champaign, 1997
[15] Grimme, E. J.; Sorensen, D. C.; Van Dooren, P., Model reduction of state space systems via an implicitly restarted Lanczos method, Numer. Algorithms, 12, 1-31 (1995) · Zbl 0870.65052
[16] Glover, K., All optimal Hankel-norm approximations of linear multivariable systems and their \(L^∞\)-error bounds, Int. J. Control, 39, 1115-1193 (1984) · Zbl 0543.93036
[17] Hammarling, S. J., Numerical solution of the stable, non-negative definite Lyapunov equation, IMA J. Numer. Anal., 2, 303-323 (1982) · Zbl 0492.65017
[18] Hodel, A. S.; Poola, K.; Tenison, B., Numerical solution of the Lyapunov equation by approximate power iteration, Linear Algebra Appl., 236, 205-230 (1996) · Zbl 0848.65033
[19] Perkins, J. E.; Helmke, U.; Moore, J. B., Balanced realizations via gradient flows, Systems Control Lett., 14, 369-380 (1990) · Zbl 0699.93010
[20] Moore, J. B.; Mahoney, R. E.; Helmke, U., Numerical gradient algorithms for eigenvalue and singular value calculations, SIAM J. Matrix Anal. Appl., SIMAX (1994) · Zbl 0808.65031
[21] Heath, M. T.; Laub, A. J.; Paige, C. H.; Ward, R. C., Computing the singular value decomposition of a product of two matrices, SIAM J. Sci. Statist. Comput., 7, 1147-1159 (1986) · Zbl 0607.65013
[22] Hu, D.; Reichel, L., Krylov-subspace methods for the Sylvester equation, Linear Algebra Appl., 172, 283-313 (1992) · Zbl 0777.65028
[23] Jaimoukha, I. M.; Kasenally, E. M., Implicitly restarted Krylov subspace methods for stable partial realizations, SIAM J. Matrix Anal. Appl., 18, 633-652 (1997) · Zbl 0873.65065
[24] 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. Automatic Control, AC-32, 115-121 (1987) · Zbl 0624.93025
[25] Moore, B. C., Principal component analysis in linear systems: controllability, observability, and model reduction, IEEE Trans. Automatic Control, AC-26, 17-32 (1981) · Zbl 0464.93022
[26] Ruhe, A., Rational Krylov algorithms for nonsymmetric eigenvalue problems II: matrix pairs, Linear Algebra Appl., 197, 283-295 (1984) · Zbl 0810.65031
[27] Saad, Y., Numerical solution of large Lyapunov equations, (in: Signal Processing, Scattering and Operator Theory, and Numerical Methods. in: Signal Processing, Scattering and Operator Theory, and Numerical Methods, Proc. MTNS-89, vol. 3 (1990), Birkhäuser: Birkhäuser Basel), 503-511
[28] Simoncini, V., On the numerical solution of \(AX − XB =C\), BIT, 36, 814-830 (1996) · Zbl 0863.65022
[29] Sorensen, D. C., Implicit application of polynomial filters in a \(k\)-step Arnoldi method, SIAM J. Matrix Anal. Appl., 13, 357-385 (1992) · Zbl 0763.65025
[30] D.C. Sorensen, Low rank approximate solutions to Lyapunov equations, Technical Report TR01-05, CAAM Deptartment, Rice University, 2001 (in preparation); D.C. Sorensen, Low rank approximate solutions to Lyapunov equations, Technical Report TR01-05, CAAM Deptartment, Rice University, 2001 (in preparation)
[31] R. Lehoucq, D.C. Sorensen, C. Yang, ARPACK Users Guide: Solution of Large Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods, SIAM Publications, Philadelphia, PA, 1998. Available from http://www.caam.rice.edu/software/ARPACK; R. Lehoucq, D.C. Sorensen, C. Yang, ARPACK Users Guide: Solution of Large Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods, SIAM Publications, Philadelphia, PA, 1998. Available from http://www.caam.rice.edu/software/ARPACK · Zbl 0901.65021
[32] Sleijpen, G. L.G.; van der Vorst, H., A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl., 17, 401-425 (1996) · Zbl 0860.65023
[33] T. Penzl, A cyclic low rank Smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput. 21 (2000) 1401-1418; T. Penzl, A cyclic low rank Smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput. 21 (2000) 1401-1418 · Zbl 0958.65052
[34] E. Wachspress, The ADI model problem, Monograph, NA Digest vol. 96, issue 36 (1996); E. Wachspress, The ADI model problem, Monograph, NA Digest vol. 96, issue 36 (1996) · Zbl 1277.65022
[35] J. Li, F. Wang, J. White, An efficient Lyapunov equation-based approach for generating reduced-order models of interconnect, in: Proc. 36th IEEE/ACM Design Automation Conference, New Orleans, LA, 1999; J. Li, F. Wang, J. White, An efficient Lyapunov equation-based approach for generating reduced-order models of interconnect, in: Proc. 36th IEEE/ACM Design Automation Conference, New Orleans, LA, 1999
[36] Kamon, M.; Wang, F.; White, J., Generating nearly optimal compact models from Krylov-subspace based reduced-order models, IEEE Trans. Circuits and Systems-II, CAS 47, 239-248 (2000)
[37] P. Van Dooren, The Lanczos algorithm and Padé approximations, Short Course, Benelux Meeting on Systems and Control, 1995; P. Van Dooren, The Lanczos algorithm and Padé approximations, Short Course, Benelux Meeting on Systems and Control, 1995
[38] Van Dooren, P., Gramian based model reduction of large-scale dynamical systems, (Numerical Analysis 2000 (2000)), 231-247 · Zbl 0952.65051
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.