Approximation of large-scale dynamical systems: an overview

• Autorzy: Athanasios C. Antoulas , Dan C. Sorensen
• Języki publikacji: EN

Abstrakty

EN

In this paper we review the state of affairs in the area of approximation of large-scale systems. We distinguish three basic categories, namely the SVD-based, the Krylov-based and the SVD-Krylov-based approximation methods. The first two were developed independently of each other and have distinct sets of attributes and drawbacks. The third approach seeks to combine the best attributes of the first two.

Słowa kluczowe

EN

SVD; Krylov; model reduction; Hankel; balancing

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2001
• Tom: 11
• Numer: 5
• Strony: 1093-1121

Daty

wydano

2001

Twórcy

autor

Athanasios C. Antoulas

• Dept. of Electrical and Computer Engineering, Rice University, Houston, TX 77005-1892, U.S.A.

autor

Dan C. Sorensen

• Dept. of Electrical and Computer Engineering, Rice University, Houston, TX 77005-1892, U.S.A.

Bibliografia

• Adamjan V.M., Arov D.Z. and Krein M.G. (1971): Analytic properties of Schmidt pairs for a Hankel operator and the generalized Schur-Takagi problem. — Math. USSR Sbornik, Vol.15, pp.31–73.
• Adamjan V.M., Arov D.Z. and Krein M.G. (1978): Infinite block Hankel matrices and related extension problems. — Amer. Math. Soc. Trans., Vol.111, pp.133–156.
• Antoulas A.C. (1993): Recursive modeling of discrete-time series, In: IMA volume on Linear Algebra for Control (P. Van Dooren and B.F. Wyman, Eds.). — pp. 1–22.
• Antoulas A.C. (1998): Approximation of linear operators in the 2-norm. — Lin. Alg. Applicns., Vol.278, pp.309–316.
• Antoulas A.C. (1999a): Approximation of linear dynamical systems, In: Wiley Encyclopedia of Electrical and Electronics Engineering, Vol.11 (J.G. Webster, Ed.). — pp.403–422.
• Antoulas A.C. (1999b): On eigenvalues and singular values of linear dynamical systems. — Proc. XVI Housholder Symp., Chateau Whistler.
• Antoulas A.C. (2002): Approximation of Large-Scale Dynamical Systems. — Philadelphia: SIAM Press (to appear).
• Antoulas A.C. and Anderson B.D.O. (1989): On the problem of stable rational interpolation. — Lin. Alg. Applicns., Vol.122–124, pp.301–329.
• Antoulas A.C. and Bishop R.H. (1987): Continued-fraction decomposition of linear systems in the state space. — Syst. Contr. Lett., Vol.9, pp.43–53.
• Antoulas A.C. and Sorensen D.C. (2001a): Projection methods for balanced model reduction. — Techn. Rep. ECE-CAAM Depts., Rice University.
• Antoulas A.C. and Van Dooren P.M. (2000): Approximation of Large-Scale Dynamical Systems. — Notes of a Short Course given at the SIAM Annual Meeting, Puerto Rico. (Notes available from the authors’ websites.)
• Antoulas A.C. and Willems J.C. (1993): A behavioral approach to linear exact modeling. — IEEE Trans. Automat. Contr., Vol.AC–38, pp.1776–1802.
• Antoulas A.C., Ball J.A., Kang J. and Willems J.C. (1990): On the solution of the minimal rational interpolation problem. — Lin. Alg. Applicns., Vol.137/138, pp.511–573.
• Antoulas A.C., Grimme E.J. and Sorensen D. (1996): On behaviors, rational interpolation and the Lanczos algorithm. — Proc. IFAC World Congress, San Francisco.
• Arnoldi W.E. (1951): The principle of minimized iterations in the solution of the matrix eigenvalue problem. — Quart. Appl. Math., Vol.9, pp.17–29.
• Avrachenkov K.E. and Lasserre J.B. (2000): Analytic perturbation of Sylvester matrix equations. — Proc. IEEE Conf. Decision and Control, Sydney.
• Bai Z. and Ye Q. (1998): Error estimation of the Padé approximation of transfer functions via the Lanczos process. — Electron. Trans. Numer. Anal., Vol.7, pp.1–17.
• Bai Z., Feldmann P. and Freund R.W. (1997): Stable and passive reduced-order models based on partial Padé approximation via the Lanczos process. — Numer. Anal. Manuscript 97–3–10, Bell Laboratories, Murray Hill.
• Bartels R.H. and Stewart G.W. (1972): Solution of the matrix equation AX + XB = C. — Comm. ACM, Vol.15, pp.820–826.
• Berkooz G., Holmes P. and Lumley J.L. (1996): Coherent Structures, Dynamical Systems and Symmetry. — Cambridge: Cambridge University Press.
• Boley D.L. (1994): Krylov space methods on state-space control models. — Circ. Syst. Signal Process., Vol.13, pp.733–758.
• Boley D.L. and Golub G.H (1984): The Lanczos algorithm and controllability. — Syst. Contr. Lett., Vol.4, pp.317–324.
• Chu M.T., Funderlic R.E. and Golub G.H. (1995): A rank-one reduction formula and its applications to matrix factorizations. — SIAM Rev., Vol.37, pp.512–530.
• Datta B.N. and Saad Y. (1991): Arnoldi methods for large Sylvester-like observer matrix equations and an associated algorithm for partial spectrum assignment. — Lin. Alg. Applicns., Vol.154–156, pp.225–244,.
• de Souza E. and Bhattacharyya S.P. (1981): Controllability, observability and the solution of AX − XB = C. — Lin. Alg. Applicns., Vol.39, pp.167–188.
• Enns D.F. (1984): Model reduction with balanced realizations: An error bound and frequency weighted generalization. — Proc. 23rd IEEE Conf. Decision and Control, pp.127–132.
• Feldmann P. and Freund R.W. (1995): Efficient linear circuit analysis by Padé approximation via the Lanczos process. — IEEE Trans. Comp.-Aided Design, Vol.14, pp.639–649.
• Fernando K.V. and Nicholson H. (1983): On the structure of balanced and other principal representations of SISO systems. — IEEE Trans. Automat. Contr., Vol.AC–28, pp.228– 231.
• Freund R.W. (1999): Reduced-order modeling techniques based on Krylov subspaces and their use in circuit simulation, In: Applied and Computational Control, Signals, and Circuits (B.N. Datta, Ed.) — Boston: Birkhäuser, Vol.1, pp.435–498.
• Gallivan K., Grimme E.J. and Van Dooren P. (1994a): Asymptotic waveform evaluation via a restarted Lanczos method. — Appl. Math. Lett., Vol.7, pp.75–80.
• Gallivan K., Grimme E. and Van Dooren P. (1994b): Padé Approximation of large-scale dynamic systems with Lanczos methods. — Proc. 33rd IEEE Conf. Decision and Control, Lake Buena Vista, FL.
• Gallivan K., Grimme E. and Van Dooren P. (1995): A rational Lanczos algorithm for model reduction. — CSRD Rep. No.1411, University of Illinois at Urbana-Champaign, IL.
• Ghavimi A.R. and Laub A.J. (1996): Numerical methods for nearly singular constrained matrix Sylvester equations. — SIAM J. Matrix Anal. Appl., Vol.17, pp.212–221.
• Glover K. (1984): All optimal Hankel-norm approximations of linear multivariable systems and their L∞ -error bounds. — Int. J. Contr., Vol.39, pp.1115–1193.
• Golub G.H. and Van Loan C.F. (1989): Matrix Computations. — Baltimore, London: The Johns Hopkins University Press.
• Gragg W.B. (1972): The Padé table and its relation to certain algorithms of numerical analysis. — SIAM Rev., Vol.14, pp.1–62.
• Gragg W.B. and Lindquist A. (1983): On the partial realization problem. — Lin. Alg. Applicns., Vol.50, pp.277–319.
• Grimme E.J. (1997): Krylov Projection Methods for Model Reduction. — Ph.D. Thesis, ECE Dept., Univ. of Illinois, Urbana-Champaign.
• Grimme E.J., Sorensen D.C. and Van Dooren P. (1995): Model reduction of state space systems via an implicitly restarted Lanczos method. — Num. Algorithms, Vol.12, pp.1– 31.
• Gutknecht M.H. (1994): The Lanczos process and Padé approximation. — Proc. Cornelius Lanczos Intl. Centenary Conf., (J.D. Brown et al., Eds.), pp.61–75, Philadelphia: SIAM.
• Heath M.T., Laub A.J., Paige C.H. and Ward R.C. (1986): Computing the singular value decomposition of a product of two matrices. — SIAM J. Sci. Stat. Computing, Vol.7, pp.1147–1159.
• Hodel A.S. and Misra P. (1997): Least-squares approximate solution of overdetermined Sylvester equations. — SIAM J. Matrix Anal. Applicns., Vol.18, pp.279–290.
• Hodel A.S., Tenison R.B. and Poola K. (1996): Numerical solution of large Lyapunov equations by approximate power iteration. — Lin. Alg. Applicns., Vol.236, pp.205–230.
• Hu D. and Reichel L. (1992): Krylov-subspace methods for the Sylvester equation. — Lin. Alg. Applicns., Vol.172, pp.283–313.
• Hubert L., Meuleman J. and Heiser W. (2000): Two purposes for matrix factorization: A historical appraisal. — SIAM Rev., Vol.42, pp.68–82.
• Jaimoukha I.M. and Kasenally E.M. (1997): Implicitly restarted Krylov subspace methods for stable partial realizations. — SIAM J. Matrix Anal. Applicns., Vol.18, pp.633–652.
• Kalman R.E. (1979): On partial realizations, transfer functions, and canonical forms. — Acta Polyt. Scand. Ma., Vol.31, pp.9–32.
• Kamon M., Wang F. and White J. (2000): Generating nearly optimal compact models from Krylov-subspace based reduced-order models. — IEEE Trans. Circuits and Systems-II: Analog and Digital Signal Process., Vol.47, pp.239–248.
• Kim S.W., Anderson B.D.O. and Madievski A.G. (1995): Error bound for transfer function order reduction using frequency weighted balanced truncation. — Syst. Contr. Lett., Vol.24, pp.183–192.
• Lall S., Marsden J.E. and Glavaski S. (1998): Empirical model reduction of controlled nonlinear systems. — Techn. Rep. CIT-CDS-98-008, California Institute of Technology.
• Lancaster P. (1970): Explicit solutions of matrix equations. — SIAM Rev., Vol.12, pp.544– 566.
• Lanczos C. (1950): An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. — J. Res. Nat. Bureau Stan., Vol.45, pp.255–282.
• Laub A.J., Heath M.T., Paige C.C. and Ward R.C. (1987): Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms. — IEEE Trans. Automat. Contr., Vol.AC–32, pp.115–121.
• Lehoucq R.B. and Salinger A.G. (2001): Large-scale eigenvalue calculations for stability analysis of steady flows on massively parallel computers. — Int. J. Numer. Meth. Fluids, Vol.36, pp.309–327.
• Lehoucq R.B., Sorensen D.C. and Yang C. (1998): ARPACK: User’s Guide. — Philadelphia: SIAM.
• Li J., Wang F. and White J. (1999): An efficient Lyapunov equation-based approach for generating reduced-order models of interconnect. — Proc. 36th IEEE/ACM Design Automation Conf., New Orleans, LA.
• Moore B.C. (1981): Principal component analysis in linear systems: Controllability, observability and model reduction. — IEEE Trans. Automat. Contr., Vol.AC–26, pp.17–32.
• Ober R. (1991): Balanced parametrization of classes of linear systems. — SIAM J. Contr. Optim., Vol.29, pp.1251–1287.
• Obinata G. and Anderson B.D.O. (2000): Model Reduction for Control System Design. — New York: Springer.
• Penzl T. (2001): A cyclic low rank Smith method for large sparse Lyapunov equations. — SIAM J. Sci. Comp. (to appear).
• Pillage L.T. and Rohrer R.A. (1990): Asymptotic waveform evaluation for timing analysis. — IEEE Trans. Comp. Aided Design, Vol.9, pp.352–366.
• Romo T.D., Clarage J.B., Sorensen D.C and Phillips Jr. G.N. (1995): Automatic identification of discrete substates in proteins: Singular value decomposition analysis of time-averaged crystallographic refinements. — Proteins: Structure, Function, and Genetics, Vol.22, pp.311–321.
• Roth W.E. (1952): The equation AX − Y B = C and AX − XB = C in matrices. — Proc. Amer. Math. Soc., Vol.3, pp.392–396.
• Ruhe A. (1984): Rational Krylov sequence methods for eigenvalue computation. — Lin. Alg. Applicns., Vol.58, pp.391—405.
• Saad Y. (1990): Numerical solution of large Lyapunov equations, In: Signal Processing, Scattering and Operator Theory, and Numerical Methods, Proc. MTNS–89 — Vol.3, pp.503– 511, Boston: Birkhäuser.
• Simoncini V. (1996): On the numerical solution of AX − XB = C. — BIT, Vol.36, pp.814– 830.
• Sorensen D.C. (1992): Implicit application of polynomial filters in a k-step Arnoldi method. — SIAM J. Matrix Anal. Applic., Vol.13, pp.357–385.
• Sorensen D.C. (1995): Implicitly restarted Arnoldi/Lanczos methods and large-scale SVD applications, In: SVD and Signal Processing III (M. Moonen and B. de Moor, Eds.) — Amsterdam: Elsevier.
• Sorensen D.C. (1999): Lecture notes on numerical methods for large scale eigenvalue problems. — Draft of lectures delivered at the Royal Institute of Technology KTH, Stockholm, Spring.
• Stroobandt D. (2000): Recent advances in system-level interconnect prediction. — IEEE Circuits and Systems Newsletter, Vol.11, pp.4–20.
• Van Dooren P. (1995): The Lanczos algorithm and Padé approximations. — Short Course, Benelux Meeting on Systems and Control.
• Van Dooren P.M. (2000): Gramian based model reduction of large-scale dynamical systems, In: Numerical Analysis 1999 — London: Chapman and Hall, CRC Press, pp.231–247.
• Varga A. (1991): Balancing-free square-root algorithms for computing singular perturbation approximations. — Proc. 30th IEEE CDC, Brighton, UK, pp.1062–1065.
• Varga A. (1995): Enhanced modal approach for model reduction. — Math. Modell. Syst., Vol.1, pp.91–105.
• Varga A. (1998): Computation of normalized coprime factorizations of rational matrices. — Syst. Contr. Lett., Vol.33, pp.37–45.
• Varga A. (1999): Model reduction routines for SLICOT, Niconet Rep. No.8. Report available from: ftp://wgs.esat.kuleuven.ac.be/pub/WGS/REPORTS/NIC1999-8.ps.Z
• Varga A. (2000): Balanced truncation model reduction of periodic systems. — Proc. IEEE CDC, Session WeP05, Sydney.
• Volkwein S. (1999): Proper orthogonal decomposition and singular value decomposition. — Tech. Rep. SFB–153, Institut für Mathematik, Universität Graz.
• Zhou K. (1995): Frequency-weighted L∞ norm and optimal Hankel norm model reduction. — IEEE Trans. Automat. Contr., Vol.AC–40, pp.1687–1699.
• Zhou K. (1999): A new balanced realization and model reduction method for unstable systems. — Proc. 14th IFAC World Congress, Beijing, Vol.D–2b–04–4, pp.123–128.