{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:42:09Z","timestamp":1740123729873,"version":"3.37.3"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T00:00:00Z","timestamp":1563840000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T00:00:00Z","timestamp":1563840000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer Algor"],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s11075-019-00776-w","type":"journal-article","created":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T14:17:40Z","timestamp":1563891460000},"page":"717-741","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Low-rank updates and divide-and-conquer methods for quadratic matrix equations"],"prefix":"10.1007","volume":"84","author":[{"given":"Daniel","family":"Kressner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick","family":"K\u00fcrschner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1813-4181","authenticated-orcid":false,"given":"Stefano","family":"Massei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,23]]},"reference":[{"key":"776_CR1","unstructured":"Abels, J., Benner, P.: CAREX - a collection of benchmark examples for continuous-time algebraic Riccati equations (Version 2.0). SLICOT working note 1999\u201314 (1999)"},{"issue":"3","key":"776_CR2","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/s10915-013-9714-z","volume":"57","author":"S Ambikasaran","year":"2013","unstructured":"Ambikasaran, S., Darve, E.: An $\\mathcal {O}(n\\log N)$ fast direct solver for partial hierarchically semi-separable matrices: with application to radial basis function interpolation. J. Sci. Comput. 57(3), 477\u2013501 (2013)","journal-title":"J. Sci. Comput."},{"issue":"3","key":"776_CR3","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s00607-006-0178-y","volume":"78","author":"U Baur","year":"2006","unstructured":"Baur, U., Benner, P.: Factorized solution of Lyapunov equations based on hierarchical matrix arithmetic. Computing 78(3), 211\u2013234 (2006)","journal-title":"Computing"},{"issue":"5","key":"776_CR4","doi-asserted-by":"crossref","first-page":"3849","DOI":"10.1137\/080741744","volume":"47","author":"B Beckermann","year":"2009","unstructured":"Beckermann, B., Reichel, L.: Error estimates and evaluation of matrix functions via the Faber transform. SIAM J. Numer. Anal. 47(5), 3849\u20133883 (2009)","journal-title":"SIAM J. Numer. Anal."},{"issue":"4","key":"776_CR5","doi-asserted-by":"crossref","first-page":"1227","DOI":"10.1137\/16M1096426","volume":"38","author":"B Beckermann","year":"2017","unstructured":"Beckermann, B., Townsend, A.: On the singular values of matrices with displacement structure. SIAM J. Matrix Anal. Appl. 38(4), 1227\u20131248 (2017)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"776_CR6","doi-asserted-by":"crossref","unstructured":"Benner, P., Bollh\u00f6fer, M., Kressner, D., Mehl, C., Stykel, T.: Numerical algebra, matrix theory, differential-algebraic equations and control theory. Springer International Publishing (2015)","DOI":"10.1007\/978-3-319-15260-8"},{"key":"776_CR7","unstructured":"Benner, P., Bujanovi\u0107, Z., K\u00fcrschner, P., Saak, J.: A numerical comparison of solvers for large-scale, continuous-time algebraic Riccati equations. Technical Report 1811.00850 arXiv (2018)"},{"issue":"2","key":"776_CR8","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/s00211-017-0907-5","volume":"138","author":"P Benner","year":"2018","unstructured":"Benner, P., Bujanovi\u0107, Z., K\u00fcrschner, P., Saak, J.: RADI: A low-rank ADI-type algorithm for large scale algebraic Riccati equations. Numer. Math. 138 (2), 301\u2013330 (2018)","journal-title":"Numer. Math."},{"key":"776_CR9","unstructured":"Benner, P., Byers, R., Mehrmann, V., Xu, H.: Robust numerical methods for robust control Technical Report 06-2004. Institut f\u00fcr Mathematik, TU Berlin (2004)"},{"issue":"9","key":"776_CR10","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1002\/nla.622","volume":"15","author":"P Benner","year":"2008","unstructured":"Benner, P., Li, J., Penzl, T.: Numerical solution of large-scale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems. Numer. Linear Algebra Appl. 15(9), 755\u2013777 (2008)","journal-title":"Numer. Linear Algebra Appl."},{"issue":"1","key":"776_CR11","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1002\/gamm.201310003","volume":"36","author":"P Benner","year":"2013","unstructured":"Benner, P., Saak, J.: Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey. GAMM-Mitt. 36(1), 32\u201352 (2013)","journal-title":"GAMM-Mitt."},{"key":"776_CR12","unstructured":"Berljafa, M., Elsworth, S., G\u00fcttel, S.: A Rational Krylov Toolbox for MATLAB MIMS EPrint 2014.56, Manchester Institute for Mathematical Sciences, The University of Manchester, UK (2014)"},{"key":"776_CR13","doi-asserted-by":"crossref","unstructured":"Bini, D.A., Favati, P., Meini, B.: A compressed cyclic reduction for QBD processes with low-rank upper and lower transitions. In: Matrix-analytic methods in stochastic models, volume 27 of Springer Proc. Math. Stat., pp. 25\u201340. Springer, New York (2013)","DOI":"10.1007\/978-1-4614-4909-6_2"},{"key":"776_CR14","volume-title":"Numerical Solution of Algebraic Riccati Equations, Volume 9 of Fundamentals of Algorithms","author":"DA Bini","year":"2012","unstructured":"Bini, D.A., Iannazzo, B., Meini, B.: Numerical Solution of Algebraic Riccati Equations, Volume 9 of Fundamentals of Algorithms. SIAM Publications, Philadelphia (2012)"},{"key":"776_CR15","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198527688.001.0001","volume-title":"Numerical methods for structured Markov chains. Numerical Mathematics and Scientific Computation","author":"DA Bini","year":"2005","unstructured":"Bini, D.A., Latouche, G., Meini, B.: Numerical methods for structured Markov chains. Numerical Mathematics and Scientific Computation. Oxford University Press, New York (2005). Oxford Science Publications"},{"key":"776_CR16","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.apnum.2016.06.014","volume":"116","author":"DA Bini","year":"2017","unstructured":"Bini, D.A., Massei, S., Robol, L.: Efficient cyclic reduction for quasi-birth-death problems with rank structured blocks. Appl. Numer Math. 116, 37\u201346 (2017)","journal-title":"Appl. Numer Math."},{"key":"776_CR17","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.laa.2016.12.027","volume":"519","author":"DA Bini","year":"2017","unstructured":"Bini, D.A., Massei, S., Robol, L.: On the decay of the off-diagonal singular values in cyclic reduction. Linear Algebra Appl. 519, 27\u201353 (2017)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"776_CR18","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s11075-008-9253-0","volume":"51","author":"DA Bini","year":"2009","unstructured":"Bini, D.A., Meini, B.: The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub. Numer. Algorithms 51(1), 23\u201360 (2009)","journal-title":"Numer. Algorithms"},{"key":"776_CR19","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.laa.2004.10.010","volume":"396","author":"EK-W Chu","year":"2005","unstructured":"Chu, E. K. -W., Fan, H. -Y., Lin, W. -W.: A structure-preserving doubling algorithm for continuous-time algebraic Riccati equations. Linear Algebra Appl. 396, 55\u201380 (2005)","journal-title":"Linear Algebra Appl."},{"key":"776_CR20","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3rd edn."},{"key":"776_CR21","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898717655","volume-title":"Numerical linear algebra and applications","author":"BN Datta","year":"2010","unstructured":"Datta, B.N.: Numerical linear algebra and applications, 2nd edn. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2010)","edition":"2nd edn."},{"issue":"8","key":"776_CR22","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1016\/j.sysconle.2011.04.013","volume":"60","author":"V Druskin","year":"2011","unstructured":"Druskin, V., Simoncini, V.: Adaptive rational Krylov subspaces for large-scale dynamical systems. Syst. Cont. Lett. 60(8), 546\u2013560 (2011)","journal-title":"Syst. Cont. Lett."},{"issue":"2","key":"776_CR23","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s00607-002-1470-0","volume":"70","author":"L Grasedyck","year":"2003","unstructured":"Grasedyck, L., Hackbusch, W., Khoromskij, B.N.: Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices. Computing 70(2), 121\u2013165 (2003)","journal-title":"Computing"},{"key":"776_CR24","doi-asserted-by":"crossref","unstructured":"Guo, C., Higham, N.J., Tisseur, F.: Detecting and solving hyperbolic quadratic eigenvalue problems. SIAM J. Matrix Anal. Appl. 30(4), 1593\u20131613 (2008\/09)","DOI":"10.1137\/070704058"},{"issue":"3","key":"776_CR25","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/s00211-005-0673-7","volume":"103","author":"X Guo","year":"2006","unstructured":"Guo, X., Lin, W., Xu, S.: A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation. Numer Math. 103(3), 393\u2013412 (2006)","journal-title":"Numer Math."},{"key":"776_CR26","unstructured":"G\u00fcttel, S.: Rational Krylov methods for operator functions. PhD thesis, TU Freiberg (2010)"},{"key":"776_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-47324-5","volume-title":"Hierarchical matrices: algorithms and analysis, Volume 49 of Springer Series in Computational Mathematics","author":"W Hackbusch","year":"2015","unstructured":"Hackbusch, W.: Hierarchical matrices: algorithms and analysis, Volume 49 of Springer Series in Computational Mathematics. Springer, Berlin (2015)"},{"issue":"11","key":"776_CR28","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1016\/j.apnum.2010.07.005","volume":"60","author":"M Heyouni","year":"2010","unstructured":"Heyouni, M.: Extended Arnoldi methods for large low-rank Sylvester matrix equations. Appl. Numer. Math. 60(11), 1171\u20131182 (2010)","journal-title":"Appl. Numer. Math."},{"issue":"4","key":"776_CR29","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1093\/imanum\/20.4.499","volume":"20","author":"NJ Higham","year":"2000","unstructured":"Higham, N.J., Kim, H.: Numerical analysis of a quadratic matrix equation. IMA J. Numer Anal. 20(4), 499\u2013519 (2000)","journal-title":"IMA J. Numer Anal."},{"issue":"2","key":"776_CR30","doi-asserted-by":"crossref","first-page":"A848","DOI":"10.1137\/17M1161038","volume":"41","author":"D Kressner","year":"2019","unstructured":"Kressner, D., Massei, S., Robol, L.: Low-rank updates and a divide-and-conquer method for linear matrix equations. SIAM J. Sci. Comput. 41(2), A848\u2013A876 (2019)","journal-title":"SIAM J. Sci. Comput."},{"issue":"2","key":"776_CR31","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1166\/sl.2006.021","volume":"4","author":"EB Feng","year":"2006","unstructured":"Feng, E.B., Rudnyi L., Koziol, D., Korvink, J.G.: Parametric model reduction for fast simulation of cyclic voltammograms. Sens. Lett. 4(2), 165\u2013173 (2006)","journal-title":"Sens. Lett."},{"key":"776_CR32","volume-title":"Lambda-matrices and vibrating systems","author":"P Lancaster","year":"2002","unstructured":"Lancaster, P.: Lambda-matrices and vibrating systems. Dover Publications, Inc., Mineola (2002). Reprint of the 1966 original [Pergamon Press, New York; MR0210345 (35 #1238)]"},{"key":"776_CR33","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198537953.001.0001","volume-title":"The Algebraic Riccati Equation","author":"P Lancaster","year":"1995","unstructured":"Lancaster, P., Rodman, L.: The Algebraic Riccati Equation. Oxford University Press, Oxford (1995)"},{"key":"776_CR34","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.laa.2015.04.006","volume":"480","author":"N Lang","year":"2015","unstructured":"Lang, N., Mena, H., Saak, J.: On the benefits of the LDLT factorization for large-scale differential matrix equation solvers. Linear Algebra Appl. 480, 44\u201371 (2015)","journal-title":"Linear Algebra Appl."},{"key":"776_CR35","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719734","volume-title":"Introduction to matrix analytic methods in stochastic modeling. ASA-SIAM Series on Statistics and Applied Probability","author":"G Latouche","year":"1999","unstructured":"Latouche, G., Ramaswami, V.: Introduction to matrix analytic methods in stochastic modeling. ASA-SIAM Series on Statistics and Applied Probability. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1999). American Statistical Association, Alexandria, VA"},{"key":"776_CR36","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-8328-3","volume-title":"Optimal control: an introduction","author":"A Locatelli","year":"2001","unstructured":"Locatelli, A.: Optimal control: an introduction. Basel, Switzerland (2001)"},{"key":"776_CR37","unstructured":"Massei, S., Robol, L.: MATLAB toolbox for HODLR and HSS matrices: hm-toolbox. Available at https:\/\/github.com\/numpi\/hm-toolbox (2017)"},{"issue":"7","key":"776_CR38","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1109\/9.1282","volume":"33","author":"V Mehrmann","year":"1988","unstructured":"Mehrmann, V., Tan, E.: Defect correction methods for the solution of algebraic Riccati equations. IEEE Trans Automat. Control 33(7), 695\u2013698 (1988)","journal-title":"IEEE Trans Automat. Control"},{"issue":"5","key":"776_CR39","doi-asserted-by":"crossref","first-page":"1550","DOI":"10.1016\/j.laa.2013.05.003","volume":"439","author":"A Melman","year":"2013","unstructured":"Melman, A.: Generalization and variations of Pellet\u2019s theorem for matrix polynomials. Linear Algebra Appl. 439(5), 1550\u20131567 (2013)","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"776_CR40","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1287\/moor.1090.0375","volume":"34","author":"M Miyazawa","year":"2009","unstructured":"Miyazawa, M.: Tail decay rates in double QBD processes and related reflected random walks. Math. Oper. Res. 34(3), 547\u2013575 (2009)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"776_CR41","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/BF01935024","volume":"34","author":"A Ruhe","year":"1994","unstructured":"Ruhe, A.: The rational Krylov algorithm for nonsymmetric eigenvalue problems. III: Complex shifts for real matrices. BIT Numer. Math. 34(1), 165\u2013176 (1994)","journal-title":"BIT Numer. Math."},{"issue":"5","key":"776_CR42","doi-asserted-by":"crossref","first-page":"1535","DOI":"10.1137\/S1064827595285597","volume":"19","author":"A Ruhe","year":"1998","unstructured":"Ruhe, A.: Rational Krylov: A practical algorithm for large sparse nonsymmetric matrix pencils. SIAM J. Sci. Comput. 19(5), 1535\u20131551 (1998)","journal-title":"SIAM J. Sci. Comput."},{"key":"776_CR43","volume-title":"Mathematics of Finite-Dimensional Control Systems, volume 43 of Lect. Notes Pure Appl Math","author":"DL Russell","year":"1979","unstructured":"Russell, D.L.: Mathematics of Finite-Dimensional Control Systems, volume 43 of Lect. Notes Pure Appl Math. Marcel Dekker Inc., New York (1979)"},{"key":"776_CR44","volume-title":"Non-negative matrices and Markov chains. Springer Series in Statistics","author":"E Seneta","year":"2006","unstructured":"Seneta, E.: Non-negative matrices and Markov chains. Springer Series in Statistics. Springer, New York (2006). Revised reprint of the second (1981) edition [Springer-Verlag, New York; MR0719544]"},{"key":"776_CR45","volume-title":"Algorithms for linear-quadratic optimization, volume 200 of Pure and Applied Mathematics","author":"V Sima","year":"1996","unstructured":"Sima, V.: Algorithms for linear-quadratic optimization, volume 200 of Pure and Applied Mathematics. Marcel Dekker, Inc., New York (1996)"},{"issue":"3","key":"776_CR46","doi-asserted-by":"crossref","first-page":"1268","DOI":"10.1137\/06066120X","volume":"29","author":"V Simoncini","year":"2007","unstructured":"Simoncini, V.: A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput. 29(3), 1268\u20131288 (2007)","journal-title":"SIAM J. Sci. Comput."},{"issue":"4","key":"776_CR47","doi-asserted-by":"crossref","first-page":"1655","DOI":"10.1137\/16M1059382","volume":"37","author":"V Simoncini","year":"2016","unstructured":"Simoncini, V.: Analysis of the rational Krylov subspace projection method for large-scale algebraic Riccati equations. SIAM J. Matrix Anal. Appl. 37(4), 1655\u20131674 (2016)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"3","key":"776_CR48","doi-asserted-by":"crossref","first-page":"904","DOI":"10.1093\/imanum\/drt015","volume":"34","author":"V Simoncini","year":"2013","unstructured":"Simoncini, V., Szyld, D.B., Monsalve, M.: On two numerical methods for the solution of large-scale algebraic Riccati equations. IMA J. Numer. Anal. 34(3), 904\u2013920 (2013)","journal-title":"IMA J. Numer. Anal."},{"issue":"1","key":"776_CR49","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0021-9045(92)90059-W","volume":"70","author":"G Starke","year":"1992","unstructured":"Starke, G.: Near-circularity for the rational Zolotarev problem in the complex plane. J. Approx. Theory 70(1), 115\u2013130 (1992)","journal-title":"J. Approx. Theory"},{"key":"776_CR50","unstructured":"The MORwiki Community. Scanning electrochemical microscopy MORwiki \u2013 Model Order Reduction Wiki (2018)"},{"issue":"1-3","key":"776_CR51","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/S0024-3795(99)00063-4","volume":"309","author":"F Tisseur","year":"2000","unstructured":"Tisseur, F.: Backward error and condition of polynomial eigenvalue problems. Linear Algebra Appl. 309(1-3), 339\u2013361 (2000)","journal-title":"Linear Algebra Appl."},{"key":"776_CR52","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1109\/TAC.1971.1099831","volume":"16","author":"JC Willems","year":"1971","unstructured":"Willems, J.C.: Least squares stationary optimal control and the algebraic Riccati Equation. IEEE Trans. Autom. Control 16, 621\u2013634 (1971)","journal-title":"IEEE Trans. Autom. Control"}],"container-title":["Numerical Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-019-00776-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11075-019-00776-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-019-00776-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,21]],"date-time":"2024-07-21T08:14:47Z","timestamp":1721549687000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11075-019-00776-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,23]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["776"],"URL":"https:\/\/doi.org\/10.1007\/s11075-019-00776-w","relation":{},"ISSN":["1017-1398","1572-9265"],"issn-type":[{"type":"print","value":"1017-1398"},{"type":"electronic","value":"1572-9265"}],"subject":[],"published":{"date-parts":[[2019,7,23]]},"assertion":[{"value":"8 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}