June 2019, 9(2): 173-186. doi: 10.3934/naco.2019013

Iterative methods for solving large sparse Lyapunov equations and application to model reduction of index 1 differential-algebraic-equations

1. 

Department of Mathematics, Hamdard University Bangladesh, Gazaria, Munshiganj, Bangladesh

2. 

Department of Mathematics and Physics, North South University, Bashundhara, Dhaka 1229, Bangladesh

Corresponding author: M. Monir Uddin (E-mail: monir.uddin@northsouth.edu)

Received  July 2017 Revised  July 2018 Published  January 2019

To implement the balancing based model reduction of large-scale dynamical systems we need to compute the low-rank (controllability and observability) Gramian factors by solving Lyapunov equations. In recent time, Rational Krylov Subspace Method (RKSM) is considered as one of the efficient methods for solving the Lyapunov equations of large-scale sparse dynamical systems. The method is well established for solving the Lyapunov equations of the standard or generalized state space systems. In this paper, we develop algorithms for solving the Lyapunov equations for large-sparse structured descriptor system of index-1. The resulting algorithm is applied for the balancing based model reduction of large sparse power system model. Numerical results are presented to show the efficiency and capability of the proposed algorithm.

Citation: M. Sumon Hossain, M. Monir Uddin. Iterative methods for solving large sparse Lyapunov equations and application to model reduction of index 1 differential-algebraic-equations. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 173-186. doi: 10.3934/naco.2019013
References:
[1]

A. C. Antoulas, Approximation of Large-Scale Dynamical Systems, SIAM Publications, Philadelphia, PA, 2005. doi: 10.1137/1.9780898718713.

[2]

R. Bartels and G. Stewart, Solution of the matrix equation AX+XB = C: Algorithm 432, Comm. ACM, 15 (1972), 820-826.

[3]

U. Baur, Control Oriented Model Reduction for Parabolic Systems, Ph.D thesis, Inst. f. Mathematik, Technische Universität Berlin, Berlin, 2008.

[4]

P. BennerP. Kürschner and J. Saak, Self-generating and efficient shift parameters in ADI methods for large Lyapunov and Sylvester equations, Elect. Trans. Numer. Anal., 43 (2014), 142-162.

[5]

P. BennerJ. R. Li and T. Penzl, Numerical solution of large Lyapunov equations, Riccati equations, and linear-quadratic control problems, Numer. Lin. Alg. Appl., 15 (2008), 755-777. doi: 10.1002/nla.622.

[6]

P. Benner, E. Quintana-Ortí and G. Quintana-Ortí, A portable subroutine library for solving linear control problems on distributed memory computers, in Workshop on wide area networks and high performance computing, Lecture Notes in Control and Information, Springer-Verlag, Berlin/Heidelberg, Germany, (1999), 61–87. doi: 10.1007/BFb0110079.

[7]

P. BennerE. Quintana-Ortí and G. Quintana-Ortí, Balanced truncation model reduction of large-scale dense systems on parallel computers, Math. Comput. Model. Dyn. Syst., 6 (2000), 383-405.

[8]

P. BennerJ. Saak and M. M. Uddin, Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control, Numer. Alg. Cont. Opt., 6 (2016), 1-20. doi: 10.3934/naco.2016.6.1.

[9]

T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM Publications, Philadelphia, PA, 2006. doi: 10.1137/1.9780898718881.

[10]

V. Druskin and L. Knizhnerman, Extended Krylov subspaces: Approximation of the matrix square root and related functions, SIAM J. Matrix Anal. Appl., 19 (1998), 755-771. doi: 10.1137/S0895479895292400.

[11]

V. Druskin and V. Simoncini, Adaptive rational Krylov subspaces for large-scale dynamical systems, Systems & Control Letters, 60 (2011), 546–560. doi: 10.1016/j.sysconle.2011.04.013.

[12]

F. FreitasJ. Rommes and N. Martins, Gramian-based reduction method applied to large sparse power system descriptor models, IEEE Transactions on Power Systems, 23 (2008), 1258-1270.

[13]

R. W. Freund, Structure-preserving model order reduction of RCL circuit equations, in Model Order Reduction: Theory, Research Aspects and Applications, Springer-Verlag, (2008), 49–73. doi: 10.1007/978-3-540-78841-6_3.

[14]

K. Glover, All optimal Hankel-norm approximations of linear multivariable systems and their L-error norms, Inter. J. Cont., 39 (1984), 1115-1193. doi: 10.1080/00207178408933239.

[15]

M. Green and D. J. N. Limebeer, Linear Robust Control, Prentice Hall, Englewood Cliffs, 1995.

[16]

S. GugercinD. Sorensen and A. Antoulas, A modified low-rank Smith method for large-scale Lyapunov equations, Numer. Alg., 32 (2003), 27-55. doi: 10.1023/A:1022205420182.

[17]

I. Jaimoukha and E. Kasenally, Krylov subspace methods for solving large Lyapunov equations, SIAM J. Numer. Anal., 31 (1994), 227-251. doi: 10.1137/0731012.

[18]

K. Jbilou, ADI preconditioned Krylov methods for large Lyapunov matrix equations, Lin. Alg. Appl., 432 (2010), 2473-2485. doi: 10.1016/j.laa.2009.12.025.

[19]

K. Jbilou and A.J. Riquet, Projection methods for large Lyapunov matrix equations, Lin. Alg. Appl., 415 (2006), 344-358. doi: 10.1016/j.laa.2004.11.004.

[20]

P. Kunkel and V. Mehrmann, Differential-Algebraic Equations: Analysis and Numerical Solution, Textbooks in Mathematics, EMS Publishing House, Zürich, Switzerland, 2006. doi: 10.4171/017.

[21]

J. R. Li, Model Reduction of Large Linear Systems via Low Rank System Gramians, Ph.D thesis, Massachusetts Institute of Technology, 2000.

[22]

J. R. Li and J. White, Low rank solution of Lyapunov equations, SIAM J. Matrix Anal. Appl., 24 (2002), 260-280. doi: 10.1137/S0895479801384937.

[23]

A. Lu and E. Wachspress, Solution of Lyapunov equations by alternating direction implicit iteration, Comput. Math. Appl., 21 (1991), 43-58. doi: 10.1016/0898-1221(91)90124-M.

[24]

T. Penzl, A cyclic low rank Smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput., 21 (2000), 1401-1418. doi: 10.1137/S1064827598347666.

[25]

A. Ruhe, The rational Krylov algorithm for nonsymmetric eigenvalue problems. Ⅲ: Complex shifts for real matrices, BIT Numerical Mathematics, 34 (1994), 165-176. doi: 10.1007/BF01935024.

[26]

Y. Saad, Numerical solution of large Lyapunov equation, in Signal Processing, Scattering, Operator Theory and Numerical Methods (Amsterdam, 1989), of Prog. Syst. Cont. Theory, Birkhäuser, Bostan, MA, (1990), 503–511.

[27]

Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, PA, USA, 2003. doi: 10.1137/1.9780898718003.

[28]

V. Simoncini, A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput., 29 (2007), 1268-1288. doi: 10.1137/06066120X.

[29]

E. D. Sontag, Mathematical Control Theory, Springer, New York, 1998. doi: 10.1007/978-1-4612-0577-7.

[30]

M. M. Uddin, Model reduction for piezo-mechanical systems using Balanced Truncation, Master's thesis, Stockholm University, Stockholm, Sweden, 2011, Available from: http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-78227.

[31]

M. M. UddinJ. SaakB. Kranz and P. Benner, Computation of a compact state space model for an adaptive spindle head configuration with piezo actuators using balanced truncation, Springer-Verlag, Production Engineering, 6 (2012), 577-586. doi: 10.1007/s11740-012-0410-x.

[32]

M. M. Uddin, S. Hossain and F. Uddin, Rational Krylov subspace method (RKSM) for solving the Lyapunov equations of index-1 descriptor systems and application to balancing based model reduction, 9th International Conference on Electrical and Computer Engineering (ICECE) 2016, (2016), 451–454. doi: 10.1155/2017/4362641.

show all references

References:
[1]

A. C. Antoulas, Approximation of Large-Scale Dynamical Systems, SIAM Publications, Philadelphia, PA, 2005. doi: 10.1137/1.9780898718713.

[2]

R. Bartels and G. Stewart, Solution of the matrix equation AX+XB = C: Algorithm 432, Comm. ACM, 15 (1972), 820-826.

[3]

U. Baur, Control Oriented Model Reduction for Parabolic Systems, Ph.D thesis, Inst. f. Mathematik, Technische Universität Berlin, Berlin, 2008.

[4]

P. BennerP. Kürschner and J. Saak, Self-generating and efficient shift parameters in ADI methods for large Lyapunov and Sylvester equations, Elect. Trans. Numer. Anal., 43 (2014), 142-162.

[5]

P. BennerJ. R. Li and T. Penzl, Numerical solution of large Lyapunov equations, Riccati equations, and linear-quadratic control problems, Numer. Lin. Alg. Appl., 15 (2008), 755-777. doi: 10.1002/nla.622.

[6]

P. Benner, E. Quintana-Ortí and G. Quintana-Ortí, A portable subroutine library for solving linear control problems on distributed memory computers, in Workshop on wide area networks and high performance computing, Lecture Notes in Control and Information, Springer-Verlag, Berlin/Heidelberg, Germany, (1999), 61–87. doi: 10.1007/BFb0110079.

[7]

P. BennerE. Quintana-Ortí and G. Quintana-Ortí, Balanced truncation model reduction of large-scale dense systems on parallel computers, Math. Comput. Model. Dyn. Syst., 6 (2000), 383-405.

[8]

P. BennerJ. Saak and M. M. Uddin, Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control, Numer. Alg. Cont. Opt., 6 (2016), 1-20. doi: 10.3934/naco.2016.6.1.

[9]

T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM Publications, Philadelphia, PA, 2006. doi: 10.1137/1.9780898718881.

[10]

V. Druskin and L. Knizhnerman, Extended Krylov subspaces: Approximation of the matrix square root and related functions, SIAM J. Matrix Anal. Appl., 19 (1998), 755-771. doi: 10.1137/S0895479895292400.

[11]

V. Druskin and V. Simoncini, Adaptive rational Krylov subspaces for large-scale dynamical systems, Systems & Control Letters, 60 (2011), 546–560. doi: 10.1016/j.sysconle.2011.04.013.

[12]

F. FreitasJ. Rommes and N. Martins, Gramian-based reduction method applied to large sparse power system descriptor models, IEEE Transactions on Power Systems, 23 (2008), 1258-1270.

[13]

R. W. Freund, Structure-preserving model order reduction of RCL circuit equations, in Model Order Reduction: Theory, Research Aspects and Applications, Springer-Verlag, (2008), 49–73. doi: 10.1007/978-3-540-78841-6_3.

[14]

K. Glover, All optimal Hankel-norm approximations of linear multivariable systems and their L-error norms, Inter. J. Cont., 39 (1984), 1115-1193. doi: 10.1080/00207178408933239.

[15]

M. Green and D. J. N. Limebeer, Linear Robust Control, Prentice Hall, Englewood Cliffs, 1995.

[16]

S. GugercinD. Sorensen and A. Antoulas, A modified low-rank Smith method for large-scale Lyapunov equations, Numer. Alg., 32 (2003), 27-55. doi: 10.1023/A:1022205420182.

[17]

I. Jaimoukha and E. Kasenally, Krylov subspace methods for solving large Lyapunov equations, SIAM J. Numer. Anal., 31 (1994), 227-251. doi: 10.1137/0731012.

[18]

K. Jbilou, ADI preconditioned Krylov methods for large Lyapunov matrix equations, Lin. Alg. Appl., 432 (2010), 2473-2485. doi: 10.1016/j.laa.2009.12.025.

[19]

K. Jbilou and A.J. Riquet, Projection methods for large Lyapunov matrix equations, Lin. Alg. Appl., 415 (2006), 344-358. doi: 10.1016/j.laa.2004.11.004.

[20]

P. Kunkel and V. Mehrmann, Differential-Algebraic Equations: Analysis and Numerical Solution, Textbooks in Mathematics, EMS Publishing House, Zürich, Switzerland, 2006. doi: 10.4171/017.

[21]

J. R. Li, Model Reduction of Large Linear Systems via Low Rank System Gramians, Ph.D thesis, Massachusetts Institute of Technology, 2000.

[22]

J. R. Li and J. White, Low rank solution of Lyapunov equations, SIAM J. Matrix Anal. Appl., 24 (2002), 260-280. doi: 10.1137/S0895479801384937.

[23]

A. Lu and E. Wachspress, Solution of Lyapunov equations by alternating direction implicit iteration, Comput. Math. Appl., 21 (1991), 43-58. doi: 10.1016/0898-1221(91)90124-M.

[24]

T. Penzl, A cyclic low rank Smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput., 21 (2000), 1401-1418. doi: 10.1137/S1064827598347666.

[25]

A. Ruhe, The rational Krylov algorithm for nonsymmetric eigenvalue problems. Ⅲ: Complex shifts for real matrices, BIT Numerical Mathematics, 34 (1994), 165-176. doi: 10.1007/BF01935024.

[26]

Y. Saad, Numerical solution of large Lyapunov equation, in Signal Processing, Scattering, Operator Theory and Numerical Methods (Amsterdam, 1989), of Prog. Syst. Cont. Theory, Birkhäuser, Bostan, MA, (1990), 503–511.

[27]

Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, PA, USA, 2003. doi: 10.1137/1.9780898718003.

[28]

V. Simoncini, A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput., 29 (2007), 1268-1288. doi: 10.1137/06066120X.

[29]

E. D. Sontag, Mathematical Control Theory, Springer, New York, 1998. doi: 10.1007/978-1-4612-0577-7.

[30]

M. M. Uddin, Model reduction for piezo-mechanical systems using Balanced Truncation, Master's thesis, Stockholm University, Stockholm, Sweden, 2011, Available from: http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-78227.

[31]

M. M. UddinJ. SaakB. Kranz and P. Benner, Computation of a compact state space model for an adaptive spindle head configuration with piezo actuators using balanced truncation, Springer-Verlag, Production Engineering, 6 (2012), 577-586. doi: 10.1007/s11740-012-0410-x.

[32]

M. M. Uddin, S. Hossain and F. Uddin, Rational Krylov subspace method (RKSM) for solving the Lyapunov equations of index-1 descriptor systems and application to balancing based model reduction, 9th International Conference on Electrical and Computer Engineering (ICECE) 2016, (2016), 451–454. doi: 10.1155/2017/4362641.

Figure 1.  Convergence histories of both Gramians by RKSM for mod-2
Figure 2.  Comparison between full system and reduced-order system in frequency domain
Figure 3.  Comparison between original system and reduced model in time domain
Figure 4.  Largest Hankel singular values of original system and 86 dimensional reduced-order system
Table 1.  Number of differential & algebraic variables and largest eigenvalue of $ (-A, E) $ for different models.
Modeldifferentialalgebraiceigs$ (-A, E) $inputs/outputs
Mod-16066 529107274/4
Mod-21 1428 593107274/4
Mod-33 07818 050106694/4
Modeldifferentialalgebraiceigs$ (-A, E) $inputs/outputs
Mod-16066 529107274/4
Mod-21 1428 593107274/4
Mod-33 07818 050106694/4
Table 2.  Comparisons between full systems and their reduced models
ModelDimensionError
fullreducedabsoluterelative
Mod-1$ 7\, 135 $ $ 87 $ $ 3.1\times 10^{-3} $ $ 1.5 \times 10^{-4} $
Mod-2$ 9\, 735 $ $ 86 $ $ 5.3 \times 10^{-2} $$ 4.7 \times 10^{-4} $
Mod-3$ 21\, 128 $ $ 77 $$ 5.6 \times 10^{-1} $$ 4.3 \times 10^{-2} $
ModelDimensionError
fullreducedabsoluterelative
Mod-1$ 7\, 135 $ $ 87 $ $ 3.1\times 10^{-3} $ $ 1.5 \times 10^{-4} $
Mod-2$ 9\, 735 $ $ 86 $ $ 5.3 \times 10^{-2} $$ 4.7 \times 10^{-4} $
Mod-3$ 21\, 128 $ $ 77 $$ 5.6 \times 10^{-1} $$ 4.3 \times 10^{-2} $
Table 3.  Balanced truncation tolerances and dimensions of reduced-order model.
Modeltolerancedimension of ROM
$ 10^{-4} $118
$ 10^{-3} $104
Mod-2 $ 10^{-2} $86
$ 10^{-1} $70
Modeltolerancedimension of ROM
$ 10^{-4} $118
$ 10^{-3} $104
Mod-2 $ 10^{-2} $86
$ 10^{-1} $70
[1]

Belinda A. Batten, Hesam Shoori, John R. Singler, Madhuka H. Weerasinghe. Balanced truncation model reduction of a nonlinear cable-mass PDE system with interior damping. Discrete & Continuous Dynamical Systems - B, 2019, 24 (1) : 83-107. doi: 10.3934/dcdsb.2018162

[2]

Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1

[3]

Qiao Liang, Qiang Ye. Deflation by restriction for the inverse-free preconditioned Krylov subspace method. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 55-71. doi: 10.3934/naco.2016.6.55

[4]

Ruijun Zhao, Yong-Tao Zhang, Shanqin Chen. Krylov implicit integration factor WENO method for SIR model with directed diffusion. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-19. doi: 10.3934/dcdsb.2019041

[5]

Guoshan Zhang, Peizhao Yu. Lyapunov method for stability of descriptor second-order and high-order systems. Journal of Industrial & Management Optimization, 2018, 14 (2) : 673-686. doi: 10.3934/jimo.2017068

[6]

Eric Chung, Yalchin Efendiev, Ke Shi, Shuai Ye. A multiscale model reduction method for nonlinear monotone elliptic equations in heterogeneous media. Networks & Heterogeneous Media, 2017, 12 (4) : 619-642. doi: 10.3934/nhm.2017025

[7]

Mohammad-Sahadet Hossain. Projection-based model reduction for time-varying descriptor systems: New results. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 73-90. doi: 10.3934/naco.2016.6.73

[8]

Chris Guiver, Mark R. Opmeer. Bounded real and positive real balanced truncation for infinite-dimensional systems. Mathematical Control & Related Fields, 2013, 3 (1) : 83-119. doi: 10.3934/mcrf.2013.3.83

[9]

Martin Redmann, Melina A. Freitag. Balanced model order reduction for linear random dynamical systems driven by Lévy noise. Journal of Computational Dynamics, 2018, 5 (1&2) : 33-59. doi: 10.3934/jcd.2018002

[10]

Dimitri Breda, Sara Della Schiava. Pseudospectral reduction to compute Lyapunov exponents of delay differential equations. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2727-2741. doi: 10.3934/dcdsb.2018092

[11]

Lars Grüne, Peter E. Kloeden, Stefan Siegmund, Fabian R. Wirth. Lyapunov's second method for nonautonomous differential equations. Discrete & Continuous Dynamical Systems - A, 2007, 18 (2&3) : 375-403. doi: 10.3934/dcds.2007.18.375

[12]

Marat Akhmet, Duygu Aruğaslan. Lyapunov-Razumikhin method for differential equations with piecewise constant argument. Discrete & Continuous Dynamical Systems - A, 2009, 25 (2) : 457-466. doi: 10.3934/dcds.2009.25.457

[13]

Heinz Schättler, Urszula Ledzewicz. Lyapunov-Schmidt reduction for optimal control problems. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 2201-2223. doi: 10.3934/dcdsb.2012.17.2201

[14]

Aihua Fan, Shilei Fan, Lingmin Liao, Yuefei Wang. Minimality of p-adic rational maps with good reduction. Discrete & Continuous Dynamical Systems - A, 2017, 37 (6) : 3161-3182. doi: 10.3934/dcds.2017135

[15]

Markus Dick, Martin Gugat, Günter Leugering. A strict $H^1$-Lyapunov function and feedback stabilization for the isothermal Euler equations with friction. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 225-244. doi: 10.3934/naco.2011.1.225

[16]

Guo Ben-Yu, Wang Zhong-Qing. Modified Chebyshev rational spectral method for the whole line. Conference Publications, 2003, 2003 (Special) : 365-374. doi: 10.3934/proc.2003.2003.365

[17]

Wei Li, Hengming Zhao, Rongcun Qin, Dianhua Wu. Constructions of optimal balanced $ (m, n, \{4, 5\}, 1) $-OOSPCs. Advances in Mathematics of Communications, 2019, 13 (2) : 329-341. doi: 10.3934/amc.2019022

[18]

Keith Burns, Katrin Gelfert. Lyapunov spectrum for geodesic flows of rank 1 surfaces. Discrete & Continuous Dynamical Systems - A, 2014, 34 (5) : 1841-1872. doi: 10.3934/dcds.2014.34.1841

[19]

Kaili Zhang, Haibin Chen, Pengfei Zhao. A potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 429-443. doi: 10.3934/jimo.2018049

[20]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]