×

Algorithms for model reduction of large dynamical systems. (English) Zbl 1092.65053

Summary: Three algorithms for the model reduction of large-scale, continuous-time, time-invariant, linear, dynamical systems with a sparse or structured transition matrix and a small number of inputs and outputs are described. They rely on low rank approximations to the controllability and observability Gramians, which can efficiently be computed by alternating directions implicit based iterative low rank methods. The first two model reduction methods are closely related to the well-known square root method and Schur method, which are balanced truncation techniques. The third method is a heuristic, balancing-free technique. The performance of the model reduction algorithms is studied in numerical experiments.

MSC:

65K10 Numerical optimization and variational techniques
65F30 Other matrix algorithms (MSC2010)
93B11 System structure simplification
93A15 Large-scale systems
65F50 Computational methods for sparse matrices
93C15 Control/observation systems governed by ordinary differential equations

Software:

Algorithm 432
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anderson, B.; Vongpanitlerd, S., Network Analysis and Synthesis (1973), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[2] Bartels, R. H.; Stewart, G. W., Solution of the matrix equation \(AX + XB =C\): Algorithm 432, Comm. ACM, 15, 820-826 (1972) · Zbl 1372.65121
[3] Benner, P.; Claver, J.; Quintana-Orti, E., Parallel distributed solvers for large stable generalized Lyapunov equations, Parallel Process. Lett., 9, 147-158 (1999)
[4] Benner, P.; Quintana-Orti, E.; Quintana-Orti, G., Balanced truncation model reduction of large-scale dense systems on parallel computers, Math. Comput. Model. Dyn. Syst., 6, 4, 383-405 (2000) · Zbl 0978.93013
[5] Cuthill, E., Several strategies for reducing the bandwidth of matrices, (Rose, D. J.; Willoughby, R. A., Sparse Matrices and Their Applications (1972), Plenum Press: Plenum Press New York)
[6] Davison, E., A method for simplifying linear dynamic systems, IEEE Trans. Automat. Control, 11, 93-101 (1966)
[8] Feldmann, P.; Freund, R., Efficient linear circuit analysis by Padé approximation via the Lanczos process, IEEE Trans. Computer-Aided Design, 14, 639-649 (1995), See also, Proc. EURO-DAC ’94 with EURO-VHDL ’94, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 170-175
[9] Fernando, K. V.; Nicholson, H., Singular perturbational model reduction of balanced systems, IEEE Trans. Automat. Control, 27, 466-468 (1982) · Zbl 0489.93006
[10] Freund, R., Reduced-order modeling techniques based on Krylov subspaces and their use in circuit simulation, (Datta, B. N., Applied and Computational Control, Signals, and Circuits, vol. 1 (1999), Birkhäuser: Birkhäuser Boston, MA), 435-498, (Chapter 9) · Zbl 0967.93008
[11] Gallivan, K.; Grimme, E.; Van Dooren, P., Asymptotic waveform evaluation via a Lanczos method, Appl. Math. Lett., 7, 75-80 (1994) · Zbl 0810.65067
[12] Gallivan, K.; Grimme, E.; Van Dooren, P., A rational Lanczos algorithm for model reduction, Numer. Algorithms, 12, 33-63 (1996) · Zbl 0870.65053
[13] Gardiner, J. D.; Laub, A. J., Parallel algorithms for algebraic Riccati equations, Internat. J. Control, 54, 1317-1333 (1991) · Zbl 0763.93036
[14] Geist, G. A., Reduction of a general matrix to tridiagonal form, SIAM J. Matrix Anal. Appl., 12, 362-373 (1991) · Zbl 0725.65039
[15] Glover, K., All optimal Hankel norm approximations of linear multivariable systems and their \(L^∞\)-error bounds, Internat. J. Control, 39, 1115-1193 (1984) · Zbl 0543.93036
[16] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore · Zbl 0865.65009
[17] Gragg, W., Matrix interpretations and applications of the continued fraction algorithm, Rocky Mountain J. Math., 4, 213-225 (1974) · Zbl 0321.65001
[18] Gudmundsson, T.; Laub, A. J., Approximate solution of large sparse Lyapunov equations, IEEE Trans. Automat. Control, 39, 1110-1114 (1994) · Zbl 0816.93041
[19] Hammarling, S. J., Numerical solution of the stable, non-negative definite Lyapunov equation, IMA J. Numer. Anal., 2, 303-323 (1982) · Zbl 0492.65017
[20] Hodel, A. S.; Poolla, K. P.; Tenison, B., Numerical solution of the Lyapunov equation by approximate power iteration, Linear Algebra Appl., 236, 205-230 (1996) · Zbl 0848.65033
[21] Hu, D. Y.; Reichel, L., Krylov-subspace methods for the Sylvester equation, Linear Algebra Appl., 172, 283-313 (1992) · Zbl 0777.65028
[22] Huhtanen, M., Iterative model reduction of large state-space systems, Int. J. Appl. Math. Comput. Sci., 9, 245-263 (1999) · Zbl 0933.93021
[23] Jaimoukha, I. M., A general minimal residual Krylov subspace method for large scale model reduction, IEEE Trans. Automat. Control, 42, 1422-1427 (1997) · Zbl 0889.93007
[24] 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
[25] Jaimoukha, I. M.; Kasenally, E. M., Oblique projection methods for large scale model reduction, SIAM J. Matrix Anal. Appl., 16, 602-627 (1995) · Zbl 0827.65073
[26] 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
[27] Kloppenburg, E.; Gilles, E. D., Automatic control of the simulated moving bed process for \(C_8\) aromatics separation using asymptotically exact input/output-linearization, J. Process Control, 9, 41-50 (1999)
[28] Lancaster, P., Explicit solutions of linear matrix equations, SIAM Rev., 12, 544-566 (1970) · Zbl 0209.06502
[29] Lancaster, P.; Rodman, L., Algebraic Riccati Equations (1995), Clarendon Press: Clarendon Press Oxford · Zbl 0836.15005
[30] LaSalle, J.; Lefschetz, S., Stability of Liapunov’s Direct Method (1961), Academic Press: Academic Press New York
[31] Mehrmann, V., (The Autonomous Linear Quadratic Control Problem, Theory and Numerical Solution. The Autonomous Linear Quadratic Control Problem, Theory and Numerical Solution, Lecture Notes in Control and Information Sciences, vol. 163 (1991), Springer-Verlag: Springer-Verlag Heidelberg) · Zbl 0746.93001
[32] Moore, B. C., Principal component analysis in linear systems: controllability, observability, and model reduction, IEEE Trans. Automat. Control, 26, 17-31 (1981) · Zbl 0464.93022
[33] Mullis, C.; Roberts, R., Roundoff noise in digital filters: frequency transformations and invariants, IEEE Trans. Acoustics, Speech, and Sign. Proc., 24, 538-550 (1976)
[34] Peaceman, D.; Rachford, H., The numerical solution of elliptic and parabolic differential equations, J. Soc. Indust. Appl. Math., 3, 28-41 (1955) · Zbl 0067.35801
[35] 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
[36] Penzl, T., Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case, Sys. Control Lett., 40, 139-144 (2000) · Zbl 0977.93034
[37] Pillage, L.; Rohrer, R., Asymptotic waveform evaluation for timing analysis, IEEE Trans. Computer-Aided Design, 9, 352-366 (1990)
[38] Roberts, J. D., Linear model reduction and solution of the algebraic Riccati equation by use of the sign function, Internat. J. Control, 32, 677-687 (1980) · Zbl 0463.93050
[39] Saad, Y., Numerical solution of large Lyapunov equations, (Kaashoek, M. A.; Van Schuppen, J. H.; Ran, A. C.M., Signal Processing, Scattering, Operator Theory and Numerical Methods (1990), Birkhäuser: Birkhäuser Boston, MA), 503-511
[40] Saad, Y., Iterative Methods for Sparse Linear Systems (1996), PWS Publishing Company · Zbl 1002.65042
[41] Safonov, M. G.; Chiang, R. Y., A Schur method for balanced-truncation model reduction, IEEE Trans. Automat. Control, 34, 729-733 (1989) · Zbl 0687.93027
[42] Schwarz, H. R., Tridiagonalization of a symmetric band matrix, Numer. Math., 12, 231-241 (1968) · Zbl 0165.50201
[43] Shamash, Y., Model reduction using the Routh stability criterion and the Padé approximation technique, Internat. J. Control, 21, 475-484 (1975) · Zbl 0299.93034
[44] Sima, V., Algorithms for Linear-Quadratic Optimization. Algorithms for Linear-Quadratic Optimization, Pure and Applied Mathematics (1996), Marcel Dekker: Marcel Dekker New York · Zbl 0863.65038
[45] Skogestad, S.; Postlethwaite, I., Multivariable feedback control (1996), John Wiley and Sons Inc.: John Wiley and Sons Inc. New York · Zbl 0842.93024
[46] Smith, R. A., Matrix equation \(XA + BX =C\), SIAM J. Appl. Math., 16 (1968) · Zbl 0157.22603
[47] Tombs, M. S.; Postlethwaite, I., Truncated balanced realization of stable, non-minimal state-space systems, Internat. J. Control, 46, 1319-1330 (1987) · Zbl 0642.93015
[48] Tröltzsch, F.; Unger, A., Fast solution of optimal control problems in the selective cooling of steel, Z. Angew. Math. Mech., 81, 447-456 (2001) · Zbl 0993.49024
[50] Wachspress, E. L., Iterative solution of the Lyapunov matrix equation, Appl. Math. Lett., 1, 87-90 (1988) · Zbl 0631.65037
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.