×

An iterative SVD-Krylov based method for model reduction of large-scale dynamical systems. (English) Zbl 1137.93006

Summary: We propose a model reduction algorithm for approximation of large-scale linear time-invariant dynamical systems. The method is a two-sided projection combining features of the singular value decomposition (SVD)-based and the Krylov-based model reduction techniques. While the SVD-side of the projection depends on the observability gramian, the Krylov-side is obtained via iterative rational Krylov steps. The reduced model is asymptotically stable, matches certain moments and solves a restricted \({\mathcal H}_2\) minimization problem. We present modifications to the proposed approach for employing low-rank gramians in the reduction step and also for reducing discrete-time systems. Several numerical examples from various disciplines verify the effectiveness of the proposed approach. It performs significantly better than the \(q\)-cover [A. Yousouff and R. E. Skelton, Covariance equivalent realizations with applications to model reduction of large-scale systems, in: C. T. Leondes (ed.), Control and Dynamic Systems, Pt. 1, Control Dyn. Syst., Adv. Theory Appl. 22, 273–348 (1985; Zbl 0651.93006); A. Yousouff, D. A. Wagie and R. E. Skelton, J. Math. Anal. Appl. 106, 91–115 (1985; Zbl 0573.93073)] and the least-squares [S. Gugercin and A. C. Antoulas, Linear Algebra Appl. 415, No. 2–3, 290–321 (2006; Zbl 1112.93015)] methods that have a similar projection structure to the proposed method. Also, in terms of both the \({\mathcal H}_2\) and \({\mathcal H}_2\) error measures, its performance is comparable to or sometimes better than that of balanced truncation. Moreover, the method proves to be robust with respect to the perturbations due to usage of approximate gramians.

MSC:

93A15 Large-scale systems
93B11 System structure simplification
93D20 Asymptotic stability in control theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Antoulas, A. C.; Ball, J. A.; Kang, J.; Willems, J. C., On the solution of the minimal rational interpolation problem, Linear Algebra Appl., 137/138, 511-573 (1990) · Zbl 0715.93020
[2] A.C. Antoulas, D.C. Sorensen, Projection methods for balanced model reduction, Trechnical Report ECE-CAAM Depts, Rice University, 1999 (September).; A.C. Antoulas, D.C. Sorensen, Projection methods for balanced model reduction, Trechnical Report ECE-CAAM Depts, Rice University, 1999 (September).
[3] A.C. Antoulas, D.C. Sorensen, The Sylvester equation and approximate balanced reduction, in: V. Blondel, D. Hinrichsen, J. Rosenthal, P.M. van Dooren (Eds.), Linear Systems and Control, Linear Algebra and Its Applications, vol. 351-352, 2002, pp. 671-700 (fourth special issue).; A.C. Antoulas, D.C. Sorensen, The Sylvester equation and approximate balanced reduction, in: V. Blondel, D. Hinrichsen, J. Rosenthal, P.M. van Dooren (Eds.), Linear Systems and Control, Linear Algebra and Its Applications, vol. 351-352, 2002, pp. 671-700 (fourth special issue). · Zbl 1023.93012
[4] Antoulas, A. C.; Sorensen, D. C.; Gugercin, S., A survey of model reduction methods for large scale systems, Contemporary Mathematics, vol. 280 (2001), AMS Publications, pp. 193-219 · Zbl 1048.93014
[5] Antoulas, A. C.; Sorensen, D. C.; Zhou, Y. K., On the decay rate of Hankel singular values and related issues, Systems Control Lett., 46, 5, 323-342 (2002) · Zbl 1003.93024
[6] Antoulas, A. C., Approximation of large-scale dynamical systems. Approximation of large-scale dynamical systems, Advances in Design and Control DC-06 (2005), SIAM: SIAM Philadelphia · Zbl 1112.93002
[7] Arnoldi, W. E., The principle of minimized iterations in the solution of the matrix eigenvalue problem, Quart. Appl. Math., 9, 17-29 (1951) · Zbl 0042.12801
[8] Bai, Z.; Day, D.; Ye, Q., ABLE: an adaptive block Lanczos method for non-Hermitian eigenvalue problems, SIAM J. Matrix Anal. Appl., 20, 4, 1060-1082 (1999) · Zbl 0932.65045
[9] Bai, Z.; Ye, Q., Error estimation on the Padé approximation of transfer functions via the Lanczos procedure, Electron. Trans. Numer. Anal., 7, 1-17 (1998) · Zbl 0913.41013
[10] Ball, J. A.; Gohberg, I.; Rodman, L., Interpolation of Rational Matrix Functions (1990), Birkhäuser Verlag: Birkhäuser Verlag Basel · Zbl 0835.41005
[11] Bartels, R. H.; Stewart, G. W., Solution of the matrix equation \(AX + XA = C\): Algorithm 432, Comm. ACM, 15, 820-826 (1972) · Zbl 1372.65121
[12] C.A. Beattie, Projection methods for model reduction of dynamical systems, SIAM Conference on Computational Science and Eng, Orlando, USA, 2005 (February).; C.A. Beattie, Projection methods for model reduction of dynamical systems, SIAM Conference on Computational Science and Eng, Orlando, USA, 2005 (February). · Zbl 1159.93317
[13] Boley, D. L., Krylov space methods on state-space control models, Circuits Systems Signal Process., 13, 733-758 (1994) · Zbl 0833.93024
[14] C.A. Beattie, S. Gugercin, Inexact solves in Krylov-based model reduction, in: Proceedings of the 45th IEEE CDC, San Diego, CA, 2006 (December).; C.A. Beattie, S. Gugercin, Inexact solves in Krylov-based model reduction, in: Proceedings of the 45th IEEE CDC, San Diego, CA, 2006 (December). · Zbl 1236.93034
[15] Benner, P.; Quintana-Orti, E. S., Solving stable generalized Lyapunov equation with the matrix sign function, Numer. Algorithms, 20, 75-100 (1999) · Zbl 0940.65035
[16] Y. Chahlaoui, P. Van Dooren, A collection of benchmark examples for model reduction of linear time invariant dynamical systems, SLICOT Working Note 2002-2: February 2002. <http://www.win.tue.nl/niconet/NIC2/benchmarks.html>; Y. Chahlaoui, P. Van Dooren, A collection of benchmark examples for model reduction of linear time invariant dynamical systems, SLICOT Working Note 2002-2: February 2002. <http://www.win.tue.nl/niconet/NIC2/benchmarks.html>
[17] J.K. Cullum, W.E. Donath, A block Lanczos algorithm for computing q algebraically largest eigenvalues and a corresponding eigenspace for large, sparse symmetric matrices, in: Proceedings of IEEE Conference on Decision and Control, 1974, pp. 505-509.; J.K. Cullum, W.E. Donath, A block Lanczos algorithm for computing q algebraically largest eigenvalues and a corresponding eigenspace for large, sparse symmetric matrices, in: Proceedings of IEEE Conference on Decision and Control, 1974, pp. 505-509.
[18] De Villemagne, C.; Skelton, R., Model reduction using a projection formulation, Internat. J. Control, 40, 2141-2169 (1987)
[19] Aliaga, J. I.; Boley, D. L.; Freund, R. W.; Hernandez, V., A Lanzcos-type method for multiple starting vectors, Math. Comp., 69, 1577-1601 (2000) · Zbl 0953.65018
[20] Gaier, D., Lectures on Complex Approximation (1987), Birkhauser
[21] Gallivan, K.; Grimme, E.; Van Dooren, P., A rational Lanczos algorithm for model reduction, Numer. Algorithms, 2, 1-2, 33-63 (1996) · Zbl 0870.65053
[22] Gallivan, K.; Vandendorpe, A.; Van Dooren, P., Sylvester equations and projection-based model reduction, J. Comput. Appl. Math., 162, 213-229 (2004) · Zbl 1044.65054
[23] Gallivan, K.; Vandendorpe, A.; Van Dooren, P., Model reduction of mimo systems via tangential interpolation, SIAM J. Matrix Anal. Appl., 26, 2, 328-349 (2004) · Zbl 1078.41016
[24] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore · Zbl 0865.65009
[25] Glover, K., All optimal Hankel-norm approximations of linear mutilvariable systems and their \(L^\infty \)-error bounds, Internat. J. Control, 39, 1115-1193 (1984) · Zbl 0543.93036
[26] 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.
[27] 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
[28] S. Gugercin, A.C. Antoulas, A comparative study of 7 model reduction algorithms, in: Proceedings of the 39th IEEE Conference on Decision and Control, Sydney, Australia, December 2000.; S. Gugercin, A.C. Antoulas, A comparative study of 7 model reduction algorithms, in: Proceedings of the 39th IEEE Conference on Decision and Control, Sydney, Australia, December 2000.
[29] S. Gugercin, A.C. Antoulas, N. Bedrossian, Approximation of the international space station 1R and 12A models, in: the Proceedings of the 40th CDC, December 2001.; S. Gugercin, A.C. Antoulas, N. Bedrossian, Approximation of the international space station 1R and 12A models, in: the Proceedings of the 40th CDC, December 2001.
[30] S. Gugercin, Projection Methods for Model Reduction of Large-scale Dynamical Systems, Ph.D. Dissertation, ECE Department, Rice University, December 2002.; S. Gugercin, Projection Methods for Model Reduction of Large-scale Dynamical Systems, Ph.D. Dissertation, ECE Department, Rice University, December 2002.
[31] Gugercin, S.; Sorensen, D. C.; Antoulas, A. C., A modified low-rank Smith method for large-scale Lyapunov equations, Numer. Algorithms, 32, 1, 27-55 (2003) · Zbl 1034.93020
[32] S. Gugercin, A.C. Antoulas, An \(\mathcal{H}_2\); S. Gugercin, A.C. Antoulas, An \(\mathcal{H}_2\)
[33] Gugercin, S.; Antoulas, A. C., Model reduction of large scale systems by least squares, Linear Algebra Appl., 415, 2-3, 290-321 (2006) · Zbl 1112.93015
[34] Gugercin, S.; Li, J. R., Smith-type methods for balanced truncation of large sparse systems, (Benner, P.; Golub, G.; Mehrmann, V.; Sorensen, D. C., Dimension Reduction of Large-Scale Systems. Dimension Reduction of Large-Scale Systems, Lecture Notes in Computational Science and Engineering, vol. 45 (2005), Springer-Verlag: Springer-Verlag Berlin/Heidelberg), ISBN 3-540-24545-6 · Zbl 1215.93026
[35] S. Gugercin, A.C. Antoulas, C.A. Beattie, \( \mathcal{H}_2\); S. Gugercin, A.C. Antoulas, C.A. Beattie, \( \mathcal{H}_2\) · Zbl 1159.93318
[36] S. Gugercin, C.A. Beattie, Inexact solves in Krylov-based model reduction of large-scale dynamical systems, in: Ninth Copper Mountain Conference on Iterative Methods, Copper Mountain, CO, 2006 (April 2-7).; S. Gugercin, C.A. Beattie, Inexact solves in Krylov-based model reduction of large-scale dynamical systems, in: Ninth Copper Mountain Conference on Iterative Methods, Copper Mountain, CO, 2006 (April 2-7).
[37] Hammarling, S., Numerical solution of the stable, non-negative definite Lyapunov equation, IMA J. Numer. Anal., 2, 303-323 (1982) · Zbl 0492.65017
[38] Hodel, A. S.; Poola, K. P.; Tenison, B., Numerical solution of the Lyapunov equation by approximate power iteration, Linear Algebra Appl., 236, 205-230 (1996) · Zbl 0848.65033
[39] Hu, D. Y.; Reichel, L., Krylov subspace methods for the Sylvester equation, Linear Algebra Appl., 172, 283-313 (1992) · Zbl 0777.65028
[40] Jaimoukha, I. M.; Kasenally, E. M., Krylov subspace methods for solving large Lyapunov equations, SIAM J. Numer. Anal., 31, 227-251 (1994) · Zbl 0798.65060
[41] Kim, H. M.; Craig, R. R., Structural dynamics analysis using an unsymmetric block Lanczos algorithm, Internat. J. Numer. Methods Engrg., 26, 2305-2318 (1988) · Zbl 0661.73062
[42] Li, J.-R.; White, J., Low rank solution of Lyapunov equations, SIAM J. Matrix Anal. Appl., 24, 1 (2002)
[43] Liu, Y.; Anderson, B. D.O., Singular perturbation approximation of balanced systems, Internat. J. Control, 50, 1379-1405 (1989) · Zbl 0688.93008
[44] Lanczos, C., An iteration method for the solution of the eigenvalue problem for linear differential and integral operators, J. Res. Nat. Bur. Standards, 45, 255-282 (1950)
[45] Meier, L.; Luenberger, D. G., Approximation of linear constant systems, IEEE Trans. Automat. Control, 12, 585-588 (1967)
[46] Moore, B. C., Principal component analysis in linear system: controllability, observability and model reduction, IEEE Trans. Automat. Control, AC-26, 17-32 (1981) · Zbl 0464.93022
[47] Mullis, C. T.; Roberts, R. A., Synthesis of minimum roundoff noise fixed point digital filters, IEEE Trans. Circuits Systems I Fund Theory Appl., CAS-23, 551-562 (1976) · Zbl 0342.93066
[48] Nikishin, A. A.; Yeremin, A. Y., Variable block CG algorithm for solving large sparse symmetric positive definite linear systems on parallel computers: I: general iterative scheme, SIAM J. Matrix Anal. Appl., 16, 1135-1153 (1995) · Zbl 0837.65029
[49] O’Leary, D. P., The block conjugate gradient algorithm and related methods, Linear Algebra Appl., 29, 293-322 (1980) · Zbl 0426.65011
[50] Penzl, T., A cyclic low-rank Smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput., 21, 4, 1401-1418 (2000) · Zbl 0958.65052
[51] T. Penzl, Algorithms for model reduction of large dynamical systems, Technical Report SFB393/99-40, Sonderforschungsbereich 393 Numerische Simulation auf massiv parallelen Rechern, TU Chemnitz, 09107, FRG, 1999. <http://www.tu-chemnitz.de/sfb393/sfb99pr.html>; T. Penzl, Algorithms for model reduction of large dynamical systems, Technical Report SFB393/99-40, Sonderforschungsbereich 393 Numerische Simulation auf massiv parallelen Rechern, TU Chemnitz, 09107, FRG, 1999. <http://www.tu-chemnitz.de/sfb393/sfb99pr.html>
[52] Penzl, T., Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case, Syst. Control Lett., 40, 139-144 (2000) · Zbl 0977.93034
[53] Ruhe, A., Rational Krylov algorithms for nonsymmetric eigenvalue problems II: matrix pairs, Linear Algebra Appl., 197, 283-295 (1994) · Zbl 0810.65031
[54] Ruhe, A., Implementation aspects of band Lanczos algotihms for computation of eigenvalues of large sparse symmetric matrices, Math. Comp., 33, 680-687 (1979) · Zbl 0443.65022
[55] 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
[56] Varga, A., Model reduction software in the SLICOT library, (Datta, B., Applied and Computational Control, Signals, and Circuits (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Boston)
[57] Yousouff, A.; Wagie, D. A.; Skelton, R. E., Linear system approximation via covariance equivalent realizations, J. Math. Anal. Appl., 196, 91-115 (1985) · Zbl 0573.93073
[58] Yousouff, A.; Skelton, R. E., Covariance equivalent realizations with applications to model reduction of large-scale systems, (Leondes, C. T., Control and Dynamic Systems, vol. 22 (1985), Academic Press), 273-348
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.