Efficient Numerical Algorithms for Balanced Stochastic Truncation

• Autorzy: Benner P. , Quintana-Orti E. S. , Quintana-Orti G.
• Języki publikacji: EN

Abstrakty

EN

We propose an efficient numerical algorithm for relative error model reduction based on balanced stochastic truncation. The method uses full-rank factors of the Gramians to be balanced versus each other and exploits the fact that for large-scale systems these Gramians are often of low numerical rank. We use the easy-to-parallelize sign function method as the major computational tool in determining these full-rank factors and demonstrate the numerical performance of the suggested implementation of balanced stochastic truncation model reduction.

Słowa kluczowe

EN

model reduction; stochastic realization; balanced truncation; sign function method; Newton's method

PL

model redukcji; metoda funkcji; metoda Newtona

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2001
• Tom: Vol. 11, no. 5
• Strony: 1123--1150
• Opis fizyczny: Bibliogr. 45 poz., wykr.

Twórcy

autor

Benner P.

• Zentrum für Technomathematik, Fachbereich 3/Mathematik und Informatik, Universität Bremen, D-28334 Bremen, Germany

autor

Quintana-Orti E. S.

• Departamento de Informática, Universidad Jaume I, 12080 Castellón, Spain

autor

Quintana-Orti G.

• Departamento de Informática, Universidad Jaume I, 12080 Castellón, Spain

Bibliografia

• [1] Anderson B.D.O. (1967a): An algebraic solution to the spectral factorization problem. - IEEE Trans. Automat. Contr., Vol. AC-12, pp. 410-414.
• [2] Anderson B.D.O. (1967b): A system theory criterion for positive real matrices. - SIAM J. Contr., Vol. 5, No. 2, pp. 171-182.
• [3] Anderson E., Bai Z., Bischof C., Demmel J., Dongarra J., Du Croz J., Greenbaum A., Hammarling S., McKenney A., Ostrouchov S. and Sorensen D. (1995): LAPACK Users' Guide, 2nd Ed. - Philadelphia, PA: SIAM.
• [4] Bai Z. and Demmel J. (1993): Design of a parallel nonsymmetric eigenroutine toolbox, Part I, Proc. 6-th SIAM Conf. Parallel Processing for Scientific Computing, pp. 391-398. SIAM, Philadelphia, PA. See also: Tech. Rep. CSD-92-718, Computer Science Division, University of California, Berkeley, CA 94720.
• [5] Bai Z., Demmel J., Dongarra J., Petitet A., Robinson H. and Stanley K. (1997): The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. - SIAM J. Sci. Comput., Vol. 18, No. 5, pp. 1446-1461.
• [6] Bartels R.H. and Stewart G.W. (1972): Solution of the matrix equation AX + XB = C: Algorithm 432. - Comm. ACM, Vol. 15, No. 9, pp. 820-826.
• [7] Benner P. (1997): Numerical solution of special algebraic Riccati equations via an exact line search method. - Proc. European Control Conf. ECC 97, Brussels, Belgium, Paper 786. (CD-ROM).
• [8] Benner P. and Byers R. (1998): An exact line search method for solving generalized continuous-time algebraic Riccati equations. - IEEE Trans. Automat. Contr., Vol. 43, No. 1, pp. 101-107.
• [9] Benner P. and Quintana-Ortí E.S. (1999): Solving stable generalized Lyapunov equations with the matrix sign function. - Numer. Algorithms, Vol. 20, No. 1, pp. 75-100.
• [10] Benner P., Claver J.M. and Quintana-Ortí E.S. (1999): Parallel distributed solvers for large stable generalized Lyapunov equations. - Parall. Process. Lett., Vol. 9, No. 1, pp. 147-158.
• [11] Benner P., Byers R., Quintana-Ortí E.S. and Quintana-Ortí G. (2000a): Solving algebraic Riccati equations on parallel computers using Newton's method with exact line search. | Parallel Comput., Vol. 26, No. 10, pp. 1345-1368.
• [12] Benner P., Quintana-Ortí E.S. and Quintana-Ortí G. (2000b): Balanced truncation model reduction of large-scale dense systems on parallel computers. - Math. Comp. Model. Dyn. Syst., Vol. 6, No. 4, pp. 383-405.
• [13] Bischof C.H. (1990): Incremental condition estimation. - SIAM J. Matrix Anal. Appl., Vol. 11, No. 2, pp. 312-322.
• [14] Blackford L.S., Choi J., Cleary A., D'Azevedo E., Demmel J., Dhillon I., Dongarra J., Hammarling S., Henry G., Petitet A., Stanley K., Walker D. and Whaley R.C. (1997): ScaLAPACK Users' Guide. - Philadelphia, PA: SIAM.
• [15] Byers R. (1987): Solving the algebraic Riccati equation with the matrix sign function. - Lin. Alg. Appl., Vol. 85, pp. 267-279.
• [16] Dennis J. and Schnabel R.B. (1983): Numerical Methods for Unconstrained Optimization and Nonlinear Equations. - Englewood Cliffs: Prentice Hall.
• [17] Desai U.B. and Pal D. (1984): A transformation approach to stochastic model reduction. - IEEE Trans. Automat. Contr., Vol. AC-29, No. 12, pp. 1097-1100.
• [18] Dongarra J.J., Sameh A. and Sorensen D. (1986): Implementation of some concurrent algorithms for matrix factorization. - Parall. Comput., Vol. 3, pp. 25-34.
• [19] Fernando K.V. and Hammarling S.J. (1988): A product induced singular value decmoposition for two matrices and balanced realization, In: Linear Algebra in Signals, Systems and Control (B.N. Datta, C.R. Johnson, M.A. Kaashoek, R. Plemmons and E. Sontag, Eds). - Philadelphia, PA: SIAM, pp. 128-140.
• [20] Gardiner J.D. and Laub A.J. (1991): Parallel algorithms for algebraic Riccati equations. - Int. J. Contr., Vol. 54, No. 6, pp. 1317-1333.
• [21] Geist A., Beguelin A., Dongarra J., Jiang W., Manchek B. and Sunderam V. (1994): PVM: Parallel Virtual Machine-A Users Guide and Tutorial for Network Parallel Computing. - Cambridge, MA: MIT Press.
• [22] Glover K. (1986): Multiplicative approximation of linear multivariable systems with L∞ error bounds. - Proc. American Control Conf., Seattle, WA, pp. 1705-1709.
• [23] Golub G.H. and Van Loan C.F. (1996): Matrix Computations, 3rd Ed. - Baltimore: Johns Hopkins University Press.
• [24] Green M. (1988a): Balanced stochastic realization. - Lin. Alg. Appl., Vol. 98, pp. 211-247.
• [25] Green M. (1988b): A relative error bound for balanced stochastic truncation. - IEEE Trans. Automat. Contr., Vol. AC-33, No.10, pp. 961-965.
• [26] Gropp W., Lusk E. and Skjellum A. (1994): Using MPI: Portable Parallel Programming with the Message-Passing Interface. - Cambridge, MA: MIT Press.
• [27] Guo C.-H. and Laub A.J. (2000): On a Newton-like method for solving algebraic Riccati equations. - SIAM J. Matrix Anal. Appl., Vol. 21, No. 2, pp. 694-698.
• [28] Hammarling S.J. (1982): Numerical solution of the stable, non-negative definite Lyapunov equation. - IMA J. Numer. Anal., Vol. 2, pp. 303-323.
• [29] Heath M.T., Laub A.J., Paige C.C. and Ward R.C. (1987): Computing the SVD of a product of two matrices. - SIAM J. Sci. Statist. Comput., Vol. 7, pp. 1147-1159.
• [30] Kenney C. and Laub A.J. (1995): The matrix sign function. - IEEE Trans. Automat. Contr., Vol. 40, No. 8, pp. 1330-1348.
• [31] Kleinman D.L. (1968): On an iterative technique for Riccati equation computations. - IEEE Trans. Automat. Contr., Vol. AC-13, No. 2, pp. 114-115.
• [32] Lancaster P. and Rodman L. (1995): The Algebraic Riccati Equation. - Oxford: Oxford University Press.
• [33] Lancaster P. and Tismenetsky M. (1985): The Theory of Matrices, 2nd Ed. - Orlando: Academic Press.
• [34] Larin V.B. and Aliev F.A. (1993): Construction of square root factor for solution of the Lyapunov matrix equation. - Syst. Contr. Lett., Vol. 20, No. 2, pp. 109-112.
• [35] Laub A.J., Heath M.T., Paige C.C. and Ward R.C. (1987): Computation of system balancing transformations and other application of simultaneous diagonalization algorithms. - IEEE Trans. Automat. Contr., Vol. 34, pp. 115-122.
• [36] Liu Y. and Anderson B.D.O. (1986): Controller reduction via stable factorization and balancing. - Int. J. Contr., Vol. 44, pp. 507-531.
• [37] Moore B.C. (1981): Principal component analysis in linear systems: Controllability, observability, and model reduction. - IEEE Trans. Automat. Contr., Vol. AC-26, No. 2, pp. 17-32.
• [38] Penzl T. (1999): Algorithms for model reduction of large dynamical systems. - Tech. Rep. SFB393/99-40, Sonderforschungsbereich 393 Numerische Simulation auf massiv parallelen Rechnern, TU Chemnitz, 09107 Chemnitz, FRG. Available from http://www.tu-chemnitz.de/sfb393/sfb99pr.html.
• [39] Penzl T. (2000): Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case. - Syst. Contr. Lett., Vol. 40, pp. 139-144.
• [40] Roberts J.D. (1980): Linear model reduction and solution of the algebraic Riccati equation by use of the sign function. - Int. J. Contr., Vol. 32, pp. 677-687. (Reprint of Technical Report No.TR-13, CUED/B-Control, Cambridge University, Engineering Department, 1971).
• [41] Safonov M.G. and Chiang R.Y. (1988): Model reduction for robust control: A Schur relative error method. - Int. J. Adapt. Cont. Sign. Process., Vol. 2, pp. 259-272.
• [42] Tombs M.S. and Postlethwaite I. (1987): Truncated balanced realization of a stable non-minimal state-space system. - Int. J. Contr., Vol. 46, No. 4, pp. 1319-1330.
• [43] Varga A. (1995): On computing high accuracy solutions of a class of Riccati equations. - Contr. Theory Adv. Technol., Vol. 10, No. 4, pp. 2005-2016.
• [44] Varga A. (1999): Task II.B.1 - selection of software for controller reduction. - SLICOT Working Note 1999-18, The Working Group on Software (WGS). Available from http://www.win.tue.nl/niconet/NIC2/reports.html.
• [45] Varga A. and Fasol K.H. (1993): A new square-root balancing-free stochastic truncation model reduction algorithm. - Prepr. 12-th IFAC World Congress, Vol. 7, pp. 153-156, Sydney, Australia.

Uwagi

Partially supported by the DAAD programme Acciones Integradas Hispano-Alemanas and Conselleria de Cultura y Educación de la Generalitat Valenciana GV99-59-1-14.