zbMATH — the first resource for mathematics

Low-rank updates and divide-and-conquer methods for quadratic matrix equations. (English) Zbl 07202187
Summary: In this work, we consider two types of large-scale quadratic matrix equations: continuous-time algebraic Riccati equations, which play a central role in optimal and robust control, and unilateral quadratic matrix equations, which arise from stochastic processes on 2D lattices and vibrating systems. We propose a simple and fast way to update the solution to such matrix equations under low-rank modifications of the coefficients. Based on this procedure, we develop a divide-and-conquer method for quadratic matrix equations with coefficients that feature a specific type of hierarchical low-rank structure, which includes banded matrices. This generalizes earlier work on linear matrix equations. Numerical experiments indicate the advantages of our newly proposed method versus iterative schemes combined with hierarchical low-rank arithmetic.
65 Numerical analysis
Full Text: DOI
[1] Abels, J., Benner, P.: CAREX - a collection of benchmark examples for continuous-time algebraic Riccati equations (Version 2.0). SLICOT working note 1999-14 (1999)
[2] Ambikasaran, S.; Darve, E., An \(\mathcal{O}(n\log N)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-501 (2013) · Zbl 1292.65030
[3] Baur, U.; Benner, P., Factorized solution of Lyapunov equations based on hierarchical matrix arithmetic, Computing, 78, 3, 211-234 (2006) · Zbl 1111.65039
[4] Beckermann, B.; Reichel, L., Error estimates and evaluation of matrix functions via the Faber transform, SIAM J. Numer. Anal., 47, 5, 3849-3883 (2009) · Zbl 1204.65041
[5] Beckermann, B.; Townsend, A., On the singular values of matrices with displacement structure, SIAM J. Matrix Anal. Appl., 38, 4, 1227-1248 (2017) · Zbl 1386.15024
[6] Benner, P., Bollhöfer, M., Kressner, D., Mehl, C., Stykel, T.: Numerical algebra, matrix theory, differential-algebraic equations and control theory. Springer International Publishing (2015) · Zbl 1322.00048
[7] Benner, P., Bujanović, Z., Kürschner, P., Saak, J.: A numerical comparison of solvers for large-scale, continuous-time algebraic Riccati equations. Technical Report 1811.00850 arXiv (2018) · Zbl 1437.65021
[8] Benner, P.; Bujanović, Z.; Kürschner, P.; Saak, J., RADI: A low-rank ADI-type algorithm for large scale algebraic Riccati equations, Numer. Math., 138, 2, 301-330 (2018) · Zbl 1385.65035
[9] Benner, P., Byers, R., Mehrmann, V., Xu, H.: Robust numerical methods for robust control Technical Report 06-2004. Institut für Mathematik, TU Berlin (2004) · Zbl 1124.93022
[10] 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-777 (2008) · Zbl 1212.65245
[11] 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-52 (2013) · Zbl 1279.65044
[12] Berljafa, M., Elsworth, S., Güttel, S.: A Rational Krylov Toolbox for MATLAB MIMS EPrint 2014.56, Manchester Institute for Mathematical Sciences, The University of Manchester, UK (2014)
[13] 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-40. Springer, New York (2013) · Zbl 1280.60045
[14] Bini, DA; Iannazzo, B.; Meini, B., Numerical Solution of Algebraic Riccati Equations, Volume 9 of Fundamentals of Algorithms (2012), Philadelphia: SIAM Publications, Philadelphia · Zbl 1244.65058
[15] Bini, DA; Latouche, G.; Meini, B., Numerical methods for structured Markov chains. Numerical Mathematics and Scientific Computation (2005), New York: Oxford University Press, New York · Zbl 1076.60002
[16] Bini, DA; Massei, S.; Robol, L., Efficient cyclic reduction for quasi-birth-death problems with rank structured blocks, Appl. Numer Math., 116, 37-46 (2017) · Zbl 1372.65122
[17] Bini, DA; Massei, S.; Robol, L., On the decay of the off-diagonal singular values in cyclic reduction, Linear Algebra Appl., 519, 27-53 (2017) · Zbl 1360.65118
[18] Bini, DA; 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-60 (2009) · Zbl 1170.65021
[19] Chu, EK-W; Fan, H-Y; Lin, W-W, A structure-preserving doubling algorithm for continuous-time algebraic Riccati equations, Linear Algebra Appl., 396, 55-80 (2005) · Zbl 1151.93340
[20] Cormen, TH; Leiserson, CE; Rivest, RL; Stein, C., Introduction to algorithms (2009), Cambridge: MIT Press, Cambridge
[21] Datta, BN, Numerical linear algebra and applications (2010), Philadelphia: Society for Industrial and Applied Mathematics (SIAM), Philadelphia
[22] Druskin, V.; Simoncini, V., Adaptive rational Krylov subspaces for large-scale dynamical systems, Syst. Cont. Lett., 60, 8, 546-560 (2011) · Zbl 1236.93035
[23] Grasedyck, L.; Hackbusch, W.; Khoromskij, BN, Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices, Computing, 70, 2, 121-165 (2003) · Zbl 1239.65026
[24] Guo, C., Higham, N.J., Tisseur, F.: Detecting and solving hyperbolic quadratic eigenvalue problems. SIAM J. Matrix Anal. Appl. 30(4), 1593-1613 (2008/09) · Zbl 1180.65042
[25] Guo, X.; Lin, W.; Xu, S., A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation, Numer Math., 103, 3, 393-412 (2006) · Zbl 1097.65055
[26] Güttel, S.: Rational Krylov methods for operator functions. PhD thesis, TU Freiberg (2010)
[27] Hackbusch, W., Hierarchical matrices: algorithms and analysis, Volume 49 of Springer Series in Computational Mathematics (2015), Berlin: Springer, Berlin · Zbl 1336.65041
[28] Heyouni, M., Extended Arnoldi methods for large low-rank Sylvester matrix equations, Appl. Numer. Math., 60, 11, 1171-1182 (2010) · Zbl 1210.65093
[29] Higham, NJ; Kim, H., Numerical analysis of a quadratic matrix equation, IMA J. Numer Anal., 20, 4, 499-519 (2000) · Zbl 0966.65040
[30] 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-A876 (2019) · Zbl 1448.65034
[31] Feng, EB; Rudnyi L.; Koziol, D.; Korvink, JG, Parametric model reduction for fast simulation of cyclic voltammograms, Sens. Lett., 4, 2, 165-173 (2006)
[32] Lancaster, P., Lambda-matrices and vibrating systems (2002), Mineola: Dover Publications, Inc., Mineola · Zbl 1048.34002
[33] Lancaster, P.; Rodman, L., The Algebraic Riccati Equation (1995), Oxford: Oxford University Press, Oxford
[34] 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-71 (2015) · Zbl 1320.65110
[35] Latouche, G.; Ramaswami, V., Introduction to matrix analytic methods in stochastic modeling. ASA-SIAM Series on Statistics and Applied Probability (1999), Philadelphia: Society for Industrial and Applied Mathematics (SIAM), Philadelphia · Zbl 0922.60001
[36] Locatelli, A., Optimal control: an introduction (2001), Switzerland: Basel, Switzerland · Zbl 1096.49500
[37] Massei, S., Robol, L.: MATLAB toolbox for HODLR and HSS matrices: hm-toolbox. Available at https://github.com/numpi/hm-toolbox (2017) · Zbl 1437.15002
[38] Mehrmann, V.; Tan, E., Defect correction methods for the solution of algebraic Riccati equations, IEEE Trans Automat. Control, 33, 7, 695-698 (1988) · Zbl 0646.93024
[39] Melman, A., Generalization and variations of Pellet’s theorem for matrix polynomials, Linear Algebra Appl., 439, 5, 1550-1567 (2013) · Zbl 1305.15029
[40] Miyazawa, M., Tail decay rates in double QBD processes and related reflected random walks, Math. Oper. Res., 34, 3, 547-575 (2009) · Zbl 1213.60151
[41] Ruhe, A., The rational Krylov algorithm for nonsymmetric eigenvalue problems. III: Complex shifts for real matrices, BIT Numer. Math., 34, 1, 165-176 (1994) · Zbl 0810.65032
[42] Ruhe, A., Rational Krylov: A practical algorithm for large sparse nonsymmetric matrix pencils, SIAM J. Sci. Comput., 19, 5, 1535-1551 (1998) · Zbl 0914.65036
[43] Russell, DL, Mathematics of Finite-Dimensional Control Systems, volume 43 of Lect. Notes Pure Appl Math (1979), New York: Marcel Dekker Inc., New York
[44] Seneta, E., Non-negative matrices and Markov chains. Springer Series in Statistics (2006), New York: Springer, New York · Zbl 1099.60004
[45] Sima, V., Algorithms for linear-quadratic optimization, volume 200 of Pure and Applied Mathematics (1996), New York: Marcel Dekker, Inc., New York · Zbl 0863.65038
[46] Simoncini, V., A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput., 29, 3, 1268-1288 (2007) · Zbl 1146.65038
[47] Simoncini, V., Analysis of the rational Krylov subspace projection method for large-scale algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 37, 4, 1655-1674 (2016) · Zbl 06655499
[48] Simoncini, V.; Szyld, DB; Monsalve, M., On two numerical methods for the solution of large-scale algebraic Riccati equations, IMA J. Numer. Anal., 34, 3, 904-920 (2013) · Zbl 1298.65083
[49] Starke, G., Near-circularity for the rational Zolotarev problem in the complex plane, J. Approx. Theory, 70, 1, 115-130 (1992) · Zbl 0758.41019
[50] The MORwiki Community. Scanning electrochemical microscopy MORwiki - Model Order Reduction Wiki (2018)
[51] Tisseur, F., Backward error and condition of polynomial eigenvalue problems, Linear Algebra Appl., 309, 1-3, 339-361 (2000) · Zbl 0955.65027
[52] Willems, JC, Least squares stationary optimal control and the algebraic Riccati Equation, IEEE Trans. Autom. Control, 16, 621-634 (1971)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.