Efficient numerical algorithms for balanced stochastic truncation

Peter Benner; Enrique Quintana-Ortí; Gregorio Quintana-Ortí

International Journal of Applied Mathematics and Computer Science (2001)

  • Volume: 11, Issue: 5, page 1123-1150
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Benner, Peter, Quintana-Ortí, Enrique, and Quintana-Ortí, Gregorio. "Efficient numerical algorithms for balanced stochastic truncation." International Journal of Applied Mathematics and Computer Science 11.5 (2001): 1123-1150. <http://eudml.org/doc/207548>.

@article{Benner2001,
abstract = {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.},
author = {Benner, Peter, Quintana-Ortí, Enrique, Quintana-Ortí, Gregorio},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {stochastic realization; Newton's method; sign function method; model reduction; balancedtruncation; balanced truncation; balanced realization; controllability grammian; observability grammian; Riccati equation; Cholesky factors; large scale systems; parallel algorithm; sign-function technique; Newton iteration; Lyapunov equation},
language = {eng},
number = {5},
pages = {1123-1150},
title = {Efficient numerical algorithms for balanced stochastic truncation},
url = {http://eudml.org/doc/207548},
volume = {11},
year = {2001},
}

TY - JOUR
AU - Benner, Peter
AU - Quintana-Ortí, Enrique
AU - Quintana-Ortí, Gregorio
TI - Efficient numerical algorithms for balanced stochastic truncation
JO - International Journal of Applied Mathematics and Computer Science
PY - 2001
VL - 11
IS - 5
SP - 1123
EP - 1150
AB - 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.
LA - eng
KW - stochastic realization; Newton's method; sign function method; model reduction; balancedtruncation; balanced truncation; balanced realization; controllability grammian; observability grammian; Riccati equation; Cholesky factors; large scale systems; parallel algorithm; sign-function technique; Newton iteration; Lyapunov equation
UR - http://eudml.org/doc/207548
ER -

References

top
  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. Zbl0158.03701
  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. Zbl0843.65018
  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. Zbl0890.65034
  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. Zbl0908.93026
  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. Zbl0940.65035
  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. Zbl0949.65041
  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. Zbl0978.93013
  13. Bischof C.H. (1990): Incremental condition estimation. — SIAM J. Matrix Anal. Appl., Vol.11, No.2, pp.312–322. Zbl0697.65042
  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. Zbl0886.65022
  15. Byers R. (1987): Solving the algebraic Riccati equation with the matrix sign function. — Lin. Alg. Appl., Vol.85, pp.267–279. Zbl0611.65027
  16. Dennis J. and Schnabel R.B. (1983): Numerical Methods for Unconstrained Optimization and Nonlinear Equations. — Englewood Cliffs: Prentice Hall. Zbl0579.65058
  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. Zbl0556.93057
  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. Zbl0591.65027
  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. Zbl0763.93036
  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. Zbl0849.68032
  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. Zbl0865.65009
  24. Green M. (1988a): Balanced stochastic realization. — Lin. Alg. Appl., Vol.98, pp.211–247. Zbl0642.93054
  25. Green M. (1988b): A relative error bound for balanced stochastic truncation. — IEEE Trans. Automat. Contr., Vol.AC–33, No.10, pp.961–965. Zbl0659.93061
  26. Gropp W., Lusk E. and Skjellum A. (1994): Using MPI: Portable Parallel Programming with the Message-Passing Interface. — Cambridge, MA: MIT Press. Zbl0875.68206
  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. Zbl0965.65067
  28. Hammarling S.J. (1982): Numerical solution of the stable, non-negative definite Lyapunov equation. — IMA J. Numer. Anal., Vol.2, pp.303–323. Zbl0492.65017
  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. Zbl0607.65013
  30. Kenney C. and Laub A.J. (1995): The matrix sign function. — IEEE Trans. Automat. Contr., Vol.40, No.8, pp.1330–1348. Zbl0830.93022
  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. Zbl0836.15005
  33. Lancaster P. and Tismenetsky M. (1985): The Theory of Matrices, 2nd Ed. — Orlando: Academic Press. Zbl0558.15001
  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. Zbl0782.93082
  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. Zbl0624.93025
  36. Liu Y. and Anderson B.D.O. (1986): Controller reduction via stable factorization and balancing. — Int. J. Contr., Vol.44, pp.507–531. Zbl0604.93020
  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. Zbl0464.93022
  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. Zbl0977.93034
  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). Zbl0463.93050
  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. Zbl0731.93013
  42. 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. Zbl0642.93015
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.