Efficient numerical algorithms for balanced stochastic truncation

• Autorzy: Peter Benner , Enrique S. Quintana-Ortí , Gregorio Quintana-Ortí
• 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

stochastic realization; Newton's method; sign function method; model reduction; balancedtruncation

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

Daty

wydano

2001

Twórcy

autor

Peter Benner

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

autor

Enrique S. Quintana-Ortí

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

autor

Gregorio Quintana-Ortí

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

Bibliografia

• Anderson B.D.O. (1967a): An algebraic solution to the spectral factorization problem. — IEEE Trans. Automat. Contr., Vol.AC–12, pp.410–414.
• Anderson B.D.O. (1967b): A system theory criterion for positive real matrices. — SIAM J. Contr., Vol.5, No.2, pp.171–182.
• 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.
• 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.
• 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.
• 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.
• 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).
• 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.
• 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.
• 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.
• 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.
• 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.
• Bischof C.H. (1990): Incremental condition estimation. — SIAM J. Matrix Anal. Appl., Vol.11, No.2, pp.312–322.
• 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.
• Byers R. (1987): Solving the algebraic Riccati equation with the matrix sign function. — Lin. Alg. Appl., Vol.85, pp.267–279.
• Dennis J. and Schnabel R.B. (1983): Numerical Methods for Unconstrained Optimization and Nonlinear Equations. — Englewood Cliffs: Prentice Hall.
• 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.
• Dongarra J.J., Sameh A. and Sorensen D. (1986): Implementation of some concurrent algorithms for matrix factorization. — Parall. Comput., Vol.3, pp.25–34.
• 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.
• Gardiner J.D. and Laub A.J. (1991): Parallel algorithms for algebraic Riccati equations. — Int. J. Contr., Vol.54, No.6, pp.1317–1333.
• 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.
• Glover K. (1986): Multiplicative approximation of linear multivariable systems with L ∞ error bounds. — Proc. American Control Conf., Seattle, WA, pp.1705–1709.
• Golub G.H. and Van Loan C.F. (1996): Matrix Computations, 3rd Ed. — Baltimore: Johns Hopkins University Press.
• Green M. (1988a): Balanced stochastic realization. — Lin. Alg. Appl., Vol.98, pp.211–247.
• Green M. (1988b): A relative error bound for balanced stochastic truncation. — IEEE Trans. Automat. Contr., Vol.AC–33, No.10, pp.961–965.
• Gropp W., Lusk E. and Skjellum A. (1994): Using MPI: Portable Parallel Programming with the Message-Passing Interface. — Cambridge, MA: MIT Press.
• 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.
• Hammarling S.J. (1982): Numerical solution of the stable, non-negative definite Lyapunov equation. — IMA J. Numer. Anal., Vol.2, pp.303–323.
• 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.
• Kenney C. and Laub A.J. (1995): The matrix sign function. — IEEE Trans. Automat. Contr., Vol.40, No.8, pp.1330–1348.
• Kleinman D.L. (1968): On an iterative technique for Riccati equation computations. — IEEE Trans. Automat. Contr., Vol.AC–13, No.2, pp.114–115.
• Lancaster P. and Rodman L. (1995): The Algebraic Riccati Equation. — Oxford: Oxford University Press.
• Lancaster P. and Tismenetsky M. (1985): The Theory of Matrices, 2nd Ed. — Orlando: Academic Press.
• 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.
• 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.
• Liu Y. and Anderson B.D.O. (1986): Controller reduction via stable factorization and balancing. — Int. J. Contr., Vol.44, pp.507–531.
• 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.
• 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.
• Penzl T. (2000): Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case. — Syst. Contr. Lett., Vol.40, pp.139–144.
• 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).
• 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.
• Tombs M.S. and Postlethwaite I. (1987): Truncated balanced realization of a stable nonminimal state-space system. — Int. J. Contr., Vol.46, No.4, pp.1319–1330.
• 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.
• 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.
• 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.