RADI: a low-rank ADI-type algorithm for large scale algebraic Riccati equations. (English) Zbl 1385.65035
The authors propose a new alternating direction implicit (ADI)-type iteration for Riccati equations. In this new algorithm, the low rank factors are built incrementally: in each step, each factor is expanded by several columns and/or rows, while keeping the elements from the previous steps intact. By setting the quadratic coefficient of the equation to zero, their method reduces to the low-rank formulation of the Lyapunov ADI method.
Reviewer: Constantin Popa (Constanţa)
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 15A24 | Matrix equations and identities |
| 65F10 | Iterative numerical methods for linear systems |
Keywords:
low rank ADI-type algorithm; algebraic Riccati equations; LYapunov ADI method; control theory; alternating direction implicit-type iterationReferences:
| [1] | Amodei, L., Buchot, J.M.: An invariant subspace method for large-scale algebraic Riccati equation. Appl. Numer. Math. 60(11), 1067-1082 (2010). doi:10.1016/j.apnum.2009.09.006 · Zbl 1227.65053 · doi:10.1016/j.apnum.2009.09.006 |
| [2] | Benner, P.; Benner, P. (ed.); Bollhöfer, M. (ed.); Kressner, D. (ed.); Mehl, C. (ed.); Stykel, T. (ed.), Theory and Numerical Solution of Differential and Algebraic Riccati Equations, 67-105 (2015), Berlin · Zbl 1322.65077 · doi:10.1007/978-3-319-15260-8_4 |
| [3] | Benner, P., Bujanović, Z.: On the solution of large-scale algebraic Riccati equations by using low-dimensional invariant subspaces. Linear Algebra Appl. 488, 430-459 (2016). doi:10.1016/j.laa.2015.09.027 · Zbl 1330.15017 · doi:10.1016/j.laa.2015.09.027 |
| [4] | Benner, P., Kürschner, P., Saak, J.: An improved numerical method for balanced truncation for symmetric second order systems. Math. Comput. Model. Dyn. Syst. 19(6), 593-615 (2013). doi:10.1080/13873954.2013.794363 · Zbl 1305.93043 · doi:10.1080/13873954.2013.794363 |
| [5] | Benner, P., Kürschner, P., Saak, J.: Efficient handling of complex shift parameters in the low-rank Cholesky factor ADI method. Numer. Algorithms 62(2), 225-251 (2013). doi:10.1007/s11075-012-9569-7 · Zbl 1267.65047 · doi:10.1007/s11075-012-9569-7 |
| [6] | Benner, P., Kürschner, P., Saak, J.: Self-generating and efficient shift parameters in ADI methods for large Lyapunov and Sylvester equations. Electr. Trans. Num. Anal. 43, 142-162 (2014) · Zbl 1312.65068 |
| [7] | Benner, P., Li, J.R., Penzl, T.: Numerical solution of large Lyapunov equations, Riccati equations, and linear-quadratic control problems. Numer. Linear Algebra Appl. 15(9), 755-777 (2008) · Zbl 1212.65245 · doi:10.1002/nla.622 |
| [8] | Benner, P., Li, R.C., Truhar, N.: On the ADI method for Sylvester equations. J. Comput. Appl. Math. 233(4), 1035-1045 (2009) · Zbl 1176.65050 · doi:10.1016/j.cam.2009.08.108 |
| [9] | Benner, P., Saak, J.: A Galerkin-Newton-ADI method for solving large-scale algebraic Riccati equations. Preprint SPP1253-090, SPP1253 (2010). http://www.am.uni-erlangen.de/home/spp1253/wiki/index.php/Preprints · Zbl 1146.65038 |
| [10] | 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). doi:10.1002/gamm.201310003 · Zbl 1279.65044 · doi:10.1002/gamm.201310003 |
| [11] | Bini, D., Iannazzo, B., Meini, B.: Numerical Solution of Algebraic Riccati Equations. Fundamentals of Algorithms. SIAM, New Delhi (2012) · Zbl 1244.65058 |
| [12] | Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 1:1-1:25 (2011). doi:10.1145/2049662.2049663 · Zbl 1365.65123 · doi:10.1145/2049662.2049663 |
| [13] | Druskin, V., Simoncini, V.: Adaptive rational Krylov subspaces for large-scale dynamical systems. Syst. Control Lett. 60(8), 546-560 (2011). doi:10.1016/j.sysconle.2011.04.013 · Zbl 1236.93035 · doi:10.1016/j.sysconle.2011.04.013 |
| [14] | Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore (2013) · Zbl 1268.65037 |
| [15] | Heinkenschloss, M., Weichelt, H.K., Benner, P., Saak, J.: An inexact low-rank Newton-ADI method for large-scale algebraic Riccati equations. Appl. Numer. Math. 108, 125-142 (2016) · Zbl 1346.65017 · doi:10.1016/j.apnum.2016.05.006 |
| [16] | Heyouni, M., Jbilou, K.: An extended block Arnoldi algorithm for large-scale solutions of the continuous-time algebraic Riccati equation. Electr. Trans. Num. Anal. 33, 53-62 (2009) · Zbl 1171.65035 |
| [17] | Korvink, JG; Rudnyi, EB; Benner, P. (ed.); Sorensen, DC (ed.); Mehrmann, V. (ed.), Oberwolfach benchmark collection, No. 45, 311-315 (2005), Berlin · doi:10.1007/3-540-27909-1_11 |
| [18] | Kürschner, P.: Efficient low-rank solution of large-scale matrix equations. Ph.D. thesis, Otto-von-Guericke-Universität Magdeburg (2016) · Zbl 1298.65083 |
| [19] | Lancaster, P., Rodman, L.: The Algebraic Riccati Equation. Oxford University Press, Oxford (1995) · Zbl 0836.15005 |
| [20] | Laub, A.J.: A Schur method for solving algebraic Riccati equations. IEEE Trans. Autom. Control AC-24, 913-921 (1979) · Zbl 0424.65013 · doi:10.1109/TAC.1979.1102178 |
| [21] | Levenberg, N., Reichel, L.: A generalized ADI iterative method. Numer. Math. 66(1), 215-233 (1993). doi:10.1007/BF01385695 · Zbl 0797.65030 · doi:10.1007/BF01385695 |
| [22] | Li, J.R., White, J.: Low rank solution of Lyapunov equations. SIAM J. Matrix Anal. Appl. 24(1), 260-280 (2002) · Zbl 1016.65024 · doi:10.1137/S0895479801384937 |
| [23] | Lin, Y., Simoncini, V.: A new subspace iteration method for the algebraic Riccati equation. Numer. Linear Algebra Appl. 22(1), 26-47 (2015). doi:10.1002/nla.1936 · Zbl 1363.65076 · doi:10.1002/nla.1936 |
| [24] | Massoudi, A., Opmeer, M.R., Reis, T.: Analysis of an iteration method for the algebraic Riccati equation. SIAM J. Matrix Anal. Appl. 37(2), 624-648 (2016). doi:10.1137/140985792 · Zbl 1339.15010 · doi:10.1137/140985792 |
| [25] | Mehrmann, V., Tan, E.: Defect correction methods for the solution of algebraic Riccati equations. IEEE Trans. Autom. Control 33, 695-698 (1988) · Zbl 0646.93024 · doi:10.1109/9.1282 |
| [26] | Overton, M.L.: Large-scale optimization of eigenvalues. SIAM J. Optim. 2(1), 88-120 (1992). doi:10.1137/0802007 · Zbl 0757.65072 · doi:10.1137/0802007 |
| [27] | Penzl, T.: Lyapack Users guide. Technical Report SFB393/00-33, Sonderforschungsbereich 393 Numerische Simulation auf massiv parallelen Rechnern, TU Chemnitz, 09107 Chemnitz, Germany (2000). http://www.tu-chemnitz.de/sfb393/sfb00pr.html · Zbl 1365.65123 |
| [28] | Ruhe, A.: The rational Krylov algorithm for nonsymmetric eigenvalue problems. III: complex shifts for real matrices. BIT 34, 165-176 (1994) · Zbl 0810.65032 · doi:10.1007/BF01935024 |
| [29] | Saak, J.: Efficient numerical solution of large scale algebraic matrix equations in PDE control and model order reduction. Ph.D. thesis, TU Chemnitz (2009). http://nbn-resolving.de/urn:nbn:de:bsz:ch1-200901642 |
| [30] | Sabino, J.: Solution of large-scale Lyapunov equations via the block modified smith method. Ph.D. Thesis, Rice University, Houston, Texas (2007). http://www.caam.rice.edu/tech_reports/2006/TR06-08.pdf · Zbl 1312.65068 |
| [31] | Silvester, D., Elman, H., Ramage, A.: Incompressible Flow and Iterative Solver Software (IFISS) version 3.2 (2012). http://www.manchester.ac.uk/ifiss · Zbl 1279.65044 |
| [32] | Simoncini, V.: A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput. 29(3), 1268-1288 (2007). doi:10.1137/06066120X · Zbl 1146.65038 · doi:10.1137/06066120X |
| [33] | Simoncini, V.: Computational methods for linear matrix equations. SIAM Rev. 38(3), 377-441 (2016) · Zbl 1386.65124 · doi:10.1137/130912839 |
| [34] | Simoncini, V., Szyld, D., Monsalve, M.: On two numerical methods for the solution of large-scale algebraic Riccati equations. IMA J. Numer. Anal. 34(3), 904-920 (2014) · Zbl 1298.65083 · doi:10.1093/imanum/drt015 |
| [35] | Wachspress, E.: Iterative solution of the Lyapunov matrix equation. Appl. Math. Lett. 107, 87-90 (1988) · Zbl 0631.65037 · doi:10.1016/0893-9659(88)90183-8 |
| [36] | Wachspress, E.: The ADI Model Problem. Springer, New York (2013). doi:10.1007/978-1-4614-5122-8 · Zbl 1277.65022 · doi:10.1007/978-1-4614-5122-8 |
| [37] | Wong, N., Balakrishnan, V.: Quadratic alternating direction implicit iteration for the fast solution of algebraic Riccati equations. In: Proceedings of International Symposium on Intelligent Signal Processing and Communication Systems, pp. 373-376 (2005) · Zbl 1322.00048 |
| [38] | Wong, N., Balakrishnan, V.: Fast positive-real balanced truncation via quadratic alternating direction implicit iteration. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 26(9), 1725-1731 (2007) · doi:10.1109/TCAD.2007.895617 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
