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.  Google Scholar

[2]

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

[3]

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

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[9]

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

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[21]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[27]

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

[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.  Google Scholar

[29]

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

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

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

[2]

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

[3]

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

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[9]

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

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[21]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[27]

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

[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.  Google Scholar

[29]

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

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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]

Jaume Llibre, Claudia Valls. Rational limit cycles of abel equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021007

[2]

Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020378

[3]

Shuang Chen, Jinqiao Duan, Ji Li. Effective reduction of a three-dimensional circadian oscillator model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020349

[4]

Masaharu Taniguchi. Axisymmetric traveling fronts in balanced bistable reaction-diffusion equations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3981-3995. doi: 10.3934/dcds.2020126

[5]

Waixiang Cao, Lueling Jia, Zhimin Zhang. A $ C^1 $ Petrov-Galerkin method and Gauss collocation method for 1D general elliptic problems and superconvergence. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 81-105. doi: 10.3934/dcdsb.2020327

[6]

Tien-Yu Lin, Bhaba R. Sarker, Chien-Jui Lin. An optimal setup cost reduction and lot size for economic production quantity model with imperfect quality and quantity discounts. Journal of Industrial & Management Optimization, 2021, 17 (1) : 467-484. doi: 10.3934/jimo.2020043

[7]

Chandra Shekhar, Amit Kumar, Shreekant Varshney, Sherif Ibrahim Ammar. $ \bf{M/G/1} $ fault-tolerant machining system with imperfection. Journal of Industrial & Management Optimization, 2021, 17 (1) : 1-28. doi: 10.3934/jimo.2019096

[8]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[9]

Beom-Seok Han, Kyeong-Hun Kim, Daehan Park. A weighted Sobolev space theory for the diffusion-wave equations with time-fractional derivatives on $ C^{1} $ domains. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021002

[10]

Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006

[11]

Yuxin Zhang. The spatially heterogeneous diffusive rabies model and its shadow system. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020357

[12]

Mikhail I. Belishev, Sergey A. Simonov. A canonical model of the one-dimensional dynamical Dirac system with boundary control. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021003

[13]

Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082

[14]

Javier Fernández, Cora Tori, Marcela Zuccalli. Lagrangian reduction of nonholonomic discrete mechanical systems by stages. Journal of Geometric Mechanics, 2020, 12 (4) : 607-639. doi: 10.3934/jgm.2020029

[15]

Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089

[16]

Adel M. Al-Mahdi, Mohammad M. Al-Gharabli, Salim A. Messaoudi. New general decay result for a system of viscoelastic wave equations with past history. Communications on Pure & Applied Analysis, 2021, 20 (1) : 389-404. doi: 10.3934/cpaa.2020273

[17]

Bopeng Rao, Zhuangyi Liu. A spectral approach to the indirect boundary control of a system of weakly coupled wave equations. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 399-414. doi: 10.3934/dcds.2009.23.399

[18]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[19]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101

[20]

Mugen Huang, Moxun Tang, Jianshe Yu, Bo Zheng. A stage structured model of delay differential equations for Aedes mosquito population suppression. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3467-3484. doi: 10.3934/dcds.2020042

 Impact Factor: 

Metrics

  • PDF downloads (115)
  • HTML views (576)
  • Cited by (0)

Other articles
by authors

[Back to Top]