2013, 3(3): 491-518. doi: 10.3934/naco.2013.3.491

## Deflating irreducible singular M-matrix algebraic Riccati equations

 1 School of Mathematical Sciences, Ocean University of China, Qingdao, 266100, China 2 Department of Mathematics, University of Texas at Arlington, P.O. Box 19408, Arlington, TX 76019, United States, United States

Received  April 2012 Revised  December 2012 Published  July 2013

A deflation technique is presented for an irreducible singular $M$-matrix Algebraic Riccati Equation (MARE). The technique improves the rate of convergence of a doubling algorithm, especially for an MARE in the critical case for which without deflation the doubling algorithm converges linearly and with deflation it converges quadratically. The deflation also improves the conditioning of the MARE in the critical case and thus enables its minimal nonnegative solution to be computed more accurately.
Citation: Wei-guo Wang, Wei-chao Wang, Ren-cang Li. Deflating irreducible singular M-matrix algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 491-518. doi: 10.3934/naco.2013.3.491
##### References:
  B. D. O. Anderson, Second-order convergent algorithms for the steady-state Riccati equation, Internat. J. Control, 28 (1978), 295-306. doi: 10.1080/00207177808922455. Google Scholar  N. G. Bean, M. M. O'Reilly and P. G. Taylor, Algorithms for return probabilities for stochastic fluid flows, Stoch. Models, 21 (2005), 149-184. doi: 10.1081/STM-200046511. Google Scholar  A. Berman and R. J. Plemmons, "Nonnegative Matrices in the Mathematical Sciences," SIAM, Philadelphia, 1994. ( This SIAM edition is a corrected reproduction of the work first published in 1979 by Academic Press, San Diego, CA.) Google Scholar  D. A. Bini, B. Meini and F. Poloni, Transforming algebraic Riccati equations into unilateral quadratic matrix equations, Numer. Math., 116 (2010), 553-578. doi: 10.1007/s00211-010-0319-2. Google Scholar  C.-Y. Chiang, E. K.-W. Chu, C.-H. Guo, T.-M. Huang, W.-W. Lin and S.-F. Xu, Convergence analysis of the doubling algorithm for several nonlinear matrix equations in the critical case, SIAM J. Matrix Anal. Appl., 31 (2009), 227-247. doi: 10.1137/080717304. Google Scholar  E. K.-W. Chu, H.-Y. Fan and W.-W. Lin, A structure-preserving doubling algorithm for continuous-time algebraic Riccati equations, Linear Algebra Appl., 396 (2005), 55-80. doi: 10.1016/j.laa.2004.10.010. Google Scholar  E. K. W. Chu, H.-Y. Fan, W. W. Lin and C. S. Wang, Structure-preserving algorithms for periodic discrete-time algebraic Riccati equations., Internat. J. Control, 77 (2004), 767-788. doi: 10.1080/00207170410001714988. Google Scholar  J. Demmel, "Applied Numerical Linear Algebra," SIAM, Philadelphia, PA, 1997. doi: 10.1137/1.9781611971446. Google Scholar  M. Fiedler, "Special Matrices and Their Applications in Numerical Mathematics," Dover Publications, Inc., Mineola, New York, 2nd ed., 2008. Google Scholar  C.-H. Guo, Nonsymmetric algebraic Riccati equations and Wiener-Hopf factorization for M-matrices, SIAM J. Matrix Anal. Appl., 23 (2001), 225-242. doi: 10.1137/S0895479800375680. Google Scholar  C.-H. Guo, A new class of nonsymmetric algebraic Riccati equations, Linear Algebra Appl., 426 (2007), 636-649. doi: 10.1016/j.laa.2007.05.044. Google Scholar  C.-H. Guo and N. Higham, Iterative solution of a nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl., 29 (2007), 396-412. doi: 10.1137/050647669. Google Scholar  C.-H. Guo, B. Iannazzo and B. Meini, On the doubling algorithm for a (shifted) nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl., 29 (2007), 1083-1100. doi: 10.1137/060660837. Google Scholar  C.-H. Guo and A. J. Laub, On the iterative solution of a class of nonsymmetric algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 22 (2000), 376-391. doi: 10.1137/S089547989834980X. Google Scholar  X. Guo, W. Lin and S. Xu, A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation, Numer. Math., 103 (2006), 393-412. doi: 10.1007/s00211-005-0673-7. Google Scholar  J. Juang, Existence of algebraic matrix Riccati equations arising in transport theory, Linear Algebra Appl., 230 (1995), 89-100. doi: 10.1016/0024-3795(93)00366-8. Google Scholar  J. Juang and W.-W. Lin, Nonsymmetric algebraic Riccati equations and Hamiltonian-like matrices, SIAM J. Matrix Anal. Appl., 20 (1998), 228-243. doi: 10.1137/S0895479897318253. Google Scholar  P. Lancaster and L. Rodman, "Algebraic Riccati Equations," Oxford University Press, New York, USA, 1995. Google Scholar  V. Ramaswami, Matrix analytic methods for stochastic fluid flows, Proceedings of the 16th International Teletraffic Congress, Edinburg, 1999, Elsevier Science, 19-30. Google Scholar  L. Rogers, Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains, Ann. Appl. Probab., 4 (1994), 390-413. doi: 10.1214/aoap/1177005065. Google Scholar  W.-G. Wang, W.-C. Wang and R.-C. Li, Deflating irreducible singular M-matrix algebraic riccati equations, Technical Report 2011-20, Department of Mathematics, University of Texas at Arlington, September 2011. Google Scholar  W.-G. Wang, W.-C. Wang and R.-C. Li, Alternating-directional doubling algorithm for M-matrix algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 33 (2012), 170-194. doi: 10.1137/110835463. Google Scholar  J. Xue, S. Xu and R.-C. Li, Accurate solutions of M-matrix algebraic Riccati equations, Numer. Math., 120 (2012), 671-700. doi: 10.1007/s00211-011-0421-0. Google Scholar  J. Xue, S. Xu and R.-C. Li, Accurate solutions of M-matrix Sylvester equations, Numer. Math., 120 (2012), 639-670. doi: 10.1007/s00211-011-0420-1. Google Scholar

show all references

##### References:
  B. D. O. Anderson, Second-order convergent algorithms for the steady-state Riccati equation, Internat. J. Control, 28 (1978), 295-306. doi: 10.1080/00207177808922455. Google Scholar  N. G. Bean, M. M. O'Reilly and P. G. Taylor, Algorithms for return probabilities for stochastic fluid flows, Stoch. Models, 21 (2005), 149-184. doi: 10.1081/STM-200046511. Google Scholar  A. Berman and R. J. Plemmons, "Nonnegative Matrices in the Mathematical Sciences," SIAM, Philadelphia, 1994. ( This SIAM edition is a corrected reproduction of the work first published in 1979 by Academic Press, San Diego, CA.) Google Scholar  D. A. Bini, B. Meini and F. Poloni, Transforming algebraic Riccati equations into unilateral quadratic matrix equations, Numer. Math., 116 (2010), 553-578. doi: 10.1007/s00211-010-0319-2. Google Scholar  C.-Y. Chiang, E. K.-W. Chu, C.-H. Guo, T.-M. Huang, W.-W. Lin and S.-F. Xu, Convergence analysis of the doubling algorithm for several nonlinear matrix equations in the critical case, SIAM J. Matrix Anal. Appl., 31 (2009), 227-247. doi: 10.1137/080717304. Google Scholar  E. K.-W. Chu, H.-Y. Fan and W.-W. Lin, A structure-preserving doubling algorithm for continuous-time algebraic Riccati equations, Linear Algebra Appl., 396 (2005), 55-80. doi: 10.1016/j.laa.2004.10.010. Google Scholar  E. K. W. Chu, H.-Y. Fan, W. W. Lin and C. S. Wang, Structure-preserving algorithms for periodic discrete-time algebraic Riccati equations., Internat. J. Control, 77 (2004), 767-788. doi: 10.1080/00207170410001714988. Google Scholar  J. Demmel, "Applied Numerical Linear Algebra," SIAM, Philadelphia, PA, 1997. doi: 10.1137/1.9781611971446. Google Scholar  M. Fiedler, "Special Matrices and Their Applications in Numerical Mathematics," Dover Publications, Inc., Mineola, New York, 2nd ed., 2008. Google Scholar  C.-H. Guo, Nonsymmetric algebraic Riccati equations and Wiener-Hopf factorization for M-matrices, SIAM J. Matrix Anal. Appl., 23 (2001), 225-242. doi: 10.1137/S0895479800375680. Google Scholar  C.-H. Guo, A new class of nonsymmetric algebraic Riccati equations, Linear Algebra Appl., 426 (2007), 636-649. doi: 10.1016/j.laa.2007.05.044. Google Scholar  C.-H. Guo and N. Higham, Iterative solution of a nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl., 29 (2007), 396-412. doi: 10.1137/050647669. Google Scholar  C.-H. Guo, B. Iannazzo and B. Meini, On the doubling algorithm for a (shifted) nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl., 29 (2007), 1083-1100. doi: 10.1137/060660837. Google Scholar  C.-H. Guo and A. J. Laub, On the iterative solution of a class of nonsymmetric algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 22 (2000), 376-391. doi: 10.1137/S089547989834980X. Google Scholar  X. Guo, W. Lin and S. Xu, A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation, Numer. Math., 103 (2006), 393-412. doi: 10.1007/s00211-005-0673-7. Google Scholar  J. Juang, Existence of algebraic matrix Riccati equations arising in transport theory, Linear Algebra Appl., 230 (1995), 89-100. doi: 10.1016/0024-3795(93)00366-8. Google Scholar  J. Juang and W.-W. Lin, Nonsymmetric algebraic Riccati equations and Hamiltonian-like matrices, SIAM J. Matrix Anal. Appl., 20 (1998), 228-243. doi: 10.1137/S0895479897318253. Google Scholar  P. Lancaster and L. Rodman, "Algebraic Riccati Equations," Oxford University Press, New York, USA, 1995. Google Scholar  V. Ramaswami, Matrix analytic methods for stochastic fluid flows, Proceedings of the 16th International Teletraffic Congress, Edinburg, 1999, Elsevier Science, 19-30. Google Scholar  L. Rogers, Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains, Ann. Appl. Probab., 4 (1994), 390-413. doi: 10.1214/aoap/1177005065. Google Scholar  W.-G. Wang, W.-C. Wang and R.-C. Li, Deflating irreducible singular M-matrix algebraic riccati equations, Technical Report 2011-20, Department of Mathematics, University of Texas at Arlington, September 2011. Google Scholar  W.-G. Wang, W.-C. Wang and R.-C. Li, Alternating-directional doubling algorithm for M-matrix algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 33 (2012), 170-194. doi: 10.1137/110835463. Google Scholar  J. Xue, S. Xu and R.-C. Li, Accurate solutions of M-matrix algebraic Riccati equations, Numer. Math., 120 (2012), 671-700. doi: 10.1007/s00211-011-0421-0. Google Scholar  J. Xue, S. Xu and R.-C. Li, Accurate solutions of M-matrix Sylvester equations, Numer. Math., 120 (2012), 639-670. doi: 10.1007/s00211-011-0420-1. Google Scholar
  Dequan Yue, Wuyi Yue. Block-partitioning matrix solution of M/M/R/N queueing system with balking, reneging and server breakdowns. Journal of Industrial & Management Optimization, 2009, 5 (3) : 417-430. doi: 10.3934/jimo.2009.5.417  Giuseppe Maria Coclite, Lorenzo di Ruvo. A note on the convergence of the solution of the Novikov equation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (6) : 2865-2899. doi: 10.3934/dcdsb.2018290  Monika Eisenmann, Etienne Emmrich, Volker Mehrmann. Convergence of the backward Euler scheme for the operator-valued Riccati differential equation with semi-definite data. Evolution Equations & Control Theory, 2019, 8 (2) : 315-342. doi: 10.3934/eect.2019017  Liming Ling. The algebraic representation for high order solution of Sasa-Satsuma equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (6) : 1975-2010. doi: 10.3934/dcdss.2016081  Vassilios A. Tsachouridis, Georgios Giantamidis, Stylianos Basagiannis, Kostas Kouramas. Formal analysis of the Schulz matrix inversion algorithm: A paradigm towards computer aided verification of general matrix flow solvers. Numerical Algebra, Control & Optimization, 2020, 10 (2) : 177-206. doi: 10.3934/naco.2019047  Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018  Brian D. O. Anderson, Shaoshuai Mou, A. Stephen Morse, Uwe Helmke. Decentralized gradient algorithm for solution of a linear equation. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 319-328. doi: 10.3934/naco.2016014  Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193  Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023  Yan Tang. Convergence analysis of a new iterative algorithm for solving split variational inclusion problems. Journal of Industrial & Management Optimization, 2020, 16 (2) : 945-964. doi: 10.3934/jimo.2018187  Yong Duan, Jian-Guo Liu. Convergence analysis of the vortex blob method for the $b$-equation. Discrete & Continuous Dynamical Systems, 2014, 34 (5) : 1995-2011. doi: 10.3934/dcds.2014.34.1995  Nur Fadhilah Ibrahim. An algorithm for the largest eigenvalue of nonhomogeneous nonnegative polynomials. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 75-91. doi: 10.3934/naco.2014.4.75  Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61  Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016  Sihem Guerarra. Positive and negative definite submatrices in an Hermitian least rank solution of the matrix equation AXA*=B. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 15-22. doi: 10.3934/naco.2019002  Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233  Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial & Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1  Lingling Lv, Zhe Zhang, Lei Zhang, Weishu Wang. An iterative algorithm for periodic sylvester matrix equations. Journal of Industrial & Management Optimization, 2018, 14 (1) : 413-425. doi: 10.3934/jimo.2017053  Frank Blume. Minimal rates of entropy convergence for rank one systems. Discrete & Continuous Dynamical Systems, 2000, 6 (4) : 773-796. doi: 10.3934/dcds.2000.6.773  József Z. Farkas, Gary T. Smith, Glenn F. Webb. A dynamic model of CT scans for quantifying doubling time of ground glass opacities using histogram analysis. Mathematical Biosciences & Engineering, 2018, 15 (5) : 1203-1224. doi: 10.3934/mbe.2018055

Impact Factor:
{"ft_lang_label":"__label__en","ft_lang_prob":0.5505322,"math_prob":0.79303914,"size":14709,"snap":"2021-31-2021-39","text_gpt3_token_len":4850,"char_repetition_ratio":0.18701123,"word_repetition_ratio":0.6643869,"special_character_ratio":0.37901965,"punctuation_ratio":0.2929076,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9872739,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-28T06:31:55Z\",\"WARC-Record-ID\":\"<urn:uuid:af679e4b-7355-4e85-81e3-0aa79ab372b1>\",\"Content-Length\":\"108340\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:de2c6a7a-5022-4446-ae7f-9b29a8aaa11f>\",\"WARC-Concurrent-To\":\"<urn:uuid:423b8ab8-c032-48d1-84a7-5ed0c7b0edb1>\",\"WARC-IP-Address\":\"107.161.80.18\",\"WARC-Target-URI\":\"https://www.aimsciences.org/article/doi/10.3934/naco.2013.3.491\",\"WARC-Payload-Digest\":\"sha1:JKHALRSINQQNOODO2LLFHDHEF3GAY7QM\",\"WARC-Block-Digest\":\"sha1:PU2HYWNLWOWDHF7P5YIPXUFTQ42T6IQF\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780060538.11_warc_CC-MAIN-20210928062408-20210928092408-00595.warc.gz\"}"}