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.
@article{bwmeta1.element.bwnjournal-article-amcv11i5p1123bwm,
author = {Benner, Peter and Quintana-Ort\'\i , Enrique and Quintana-Ort\'\i , Gregorio},
title = {Efficient numerical algorithms for balanced stochastic truncation},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {11},
year = {2001},
pages = {1123-1150},
zbl = {1008.93014},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv11i5p1123bwm}
}
Benner, Peter; Quintana-Ortí, Enrique; Quintana-Ortí, Gregorio. Efficient numerical algorithms for balanced stochastic truncation. International Journal of Applied Mathematics and Computer Science, Tome 11 (2001) pp. 1123-1150. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv11i5p1123bwm/
[000] Anderson B.D.O. (1967a): An algebraic solution to the spectral factorization problem. — IEEE Trans. Automat. Contr., Vol.AC–12, pp.410–414.
[001] Anderson B.D.O. (1967b): A system theory criterion for positive real matrices. — SIAM J. Contr., Vol.5, No.2, pp.171–182. | Zbl 0158.03701
[002] 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. | Zbl 0843.65018
[003] 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.
[004] 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. | Zbl 0890.65034
[005] 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.
[006] 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).
[007] 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. | Zbl 0908.93026
[008] 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. | Zbl 0940.65035
[009] 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.
[010] 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. | Zbl 0949.65041
[011] 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. | Zbl 0978.93013
[012] Bischof C.H. (1990): Incremental condition estimation. — SIAM J. Matrix Anal. Appl., Vol.11, No.2, pp.312–322. | Zbl 0697.65042
[013] 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. | Zbl 0886.65022
[014] Byers R. (1987): Solving the algebraic Riccati equation with the matrix sign function. — Lin. Alg. Appl., Vol.85, pp.267–279. | Zbl 0611.65027
[015] Dennis J. and Schnabel R.B. (1983): Numerical Methods for Unconstrained Optimization and Nonlinear Equations. — Englewood Cliffs: Prentice Hall. | Zbl 0579.65058
[016] 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. | Zbl 0556.93057
[017] Dongarra J.J., Sameh A. and Sorensen D. (1986): Implementation of some concurrent algorithms for matrix factorization. — Parall. Comput., Vol.3, pp.25–34. | Zbl 0591.65027
[018] 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.
[019] Gardiner J.D. and Laub A.J. (1991): Parallel algorithms for algebraic Riccati equations. — Int. J. Contr., Vol.54, No.6, pp.1317–1333. | Zbl 0763.93036
[020] 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. | Zbl 0849.68032
[021] Glover K. (1986): Multiplicative approximation of linear multivariable systems with L ∞ error bounds. — Proc. American Control Conf., Seattle, WA, pp.1705–1709.
[022] Golub G.H. and Van Loan C.F. (1996): Matrix Computations, 3rd Ed. — Baltimore: Johns Hopkins University Press. | Zbl 0865.65009
[023] Green M. (1988a): Balanced stochastic realization. — Lin. Alg. Appl., Vol.98, pp.211–247. | Zbl 0642.93054
[024] Green M. (1988b): A relative error bound for balanced stochastic truncation. — IEEE Trans. Automat. Contr., Vol.AC–33, No.10, pp.961–965. | Zbl 0659.93061
[025] Gropp W., Lusk E. and Skjellum A. (1994): Using MPI: Portable Parallel Programming with the Message-Passing Interface. — Cambridge, MA: MIT Press. | Zbl 0875.68206
[026] 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. | Zbl 0965.65067
[027] Hammarling S.J. (1982): Numerical solution of the stable, non-negative definite Lyapunov equation. — IMA J. Numer. Anal., Vol.2, pp.303–323. | Zbl 0492.65017
[028] 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. | Zbl 0607.65013
[029] Kenney C. and Laub A.J. (1995): The matrix sign function. — IEEE Trans. Automat. Contr., Vol.40, No.8, pp.1330–1348. | Zbl 0830.93022
[030] Kleinman D.L. (1968): On an iterative technique for Riccati equation computations. — IEEE Trans. Automat. Contr., Vol.AC–13, No.2, pp.114–115.
[031] Lancaster P. and Rodman L. (1995): The Algebraic Riccati Equation. — Oxford: Oxford University Press. | Zbl 0836.15005
[032] Lancaster P. and Tismenetsky M. (1985): The Theory of Matrices, 2nd Ed. — Orlando: Academic Press. | Zbl 0558.15001
[033] 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. | Zbl 0782.93082
[034] 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. | Zbl 0624.93025
[035] Liu Y. and Anderson B.D.O. (1986): Controller reduction via stable factorization and balancing. — Int. J. Contr., Vol.44, pp.507–531. | Zbl 0604.93020
[036] 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. | Zbl 0464.93022
[037] 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.
[038] Penzl T. (2000): Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case. — Syst. Contr. Lett., Vol.40, pp.139–144. | Zbl 0977.93034
[039] 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). | Zbl 0463.93050
[040] 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. | Zbl 0731.93013
[041] 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. | Zbl 0642.93015
[042] 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.
[043] 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.
[044] 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.