×
Benner, Peter; Kürschner, Patrick; Saak, Jens

Low-rank Newton-ADI methods for large nonsymmetric algebraic Riccati equations. (English) Zbl 1336.93056

J. Franklin Inst. 353, No. 5, 1147-1167 (2016).
Summary: The numerical treatment of large-scale, Nonsymmetric Algebraic Riccati Equations (NAREs) by a low-rank variant of Newtons method is considered. We discuss a method to compute approximations to the solution of the NARE in a factorized form of low rank. The occurring large-scale Sylvester equations are dealt with using the Factored Alternating Direction implicit Iteration (FADI). Several performance enhancing strategies available for the factored ADI as well as the related Newton-ADI for symmetric algebraic Riccati equations are generalized to this combination. This includes the efficient computation of the norm of the residual matrix, adapted shift parameter strategies for FADI, and an acceleration of Newtons scheme by means of a Galerkin projection. Numerical experiments illustrate the capabilities of the proposed method to solve high-dimensional NAREs.

Cited in 10 Documents

MSC:

93B40 Computational methods in systems theory (MSC2010)
93C15 Control/observation systems governed by ordinary differential equations
93A15 Large-scale systems
65F10 Iterative numerical methods for linear systems

Keywords:

low-rank Newton-alternating direction implicit iteration (ADI) methods; large nonsymmetric algebraic Riccati equations; norm of residual matrix; adapted shift parameter strategies for FADI; acceleration of Newtons scheme; Galerkin projection

Software:

Algorithm 432; mftoolbox
Cite Review PDF
Full Text: DOI

References:

[1] Abou-Kandil, H.; Freiling, G.; Ionescu, V.; Jank, G., Matrix Riccati Equations in Control and Systems Theory (2003), Birkhauser: Birkhauser Basel · Zbl 1027.93001
[5] Benner, P.; Faßbender, H., On the numerical solution of large-scale sparse discrete-time Riccati equations, Adv. Comput. Math., 35, 119-147 (2011) · Zbl 1230.65070
[6] Benner, P.; Kürschner, P., Computing real low-rank solutions of Sylvester equations by the factored ADI method, Comput. Math. Appl., 67, 1656-1672 (2014) · Zbl 1364.65093
[7] Benner, P.; Kürschner, P.; Saak, J., Self-generating and efficient shift parameters in ADI methods for large Lyapunov and Sylvester equations, Electron. Trans. Numer. Anal., 43, 142-162 (2014) · Zbl 1312.65068
[8] 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, 755-777 (2008) · Zbl 1212.65245
[9] Benner, P.; Li, R.-C.; Truhar, N., On the ADI method for Sylvester equations, J. Comput. Appl. Math., 233, 1035-1045 (2009) · Zbl 1176.65050
[12] 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 Mitteilungen, 36, 32-52 (2013) · Zbl 1279.65044
[14] Bini, D. A.; Iannazzo, B.; Poloni, F., A fast Newton׳s method for a nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl., 30, 276-290 (2008) · Zbl 1166.15300
[15] Bouhamidi, A.; Hached, M.; Heyouni, M.; Jbilou, K., A preconditioned block Arnoldi method for large Sylvester matrix equations, Numer. Linear Algebra Appl., 20, 208-219 (2011) · Zbl 1289.65099
[16] Brandts, J., The Riccati algorithm for eigenvalues and invariant subspaces of matrices with inexpensive action, Linear Algebra Appl., 358, 335-365 (2003) · Zbl 1030.65022
[17] De Moor, B.; David, J., Total linear least squares and the algebraic Riccati equation, Syst. Control Lett., 18, 329-337 (1992) · Zbl 0763.93085
[18] Demmel, J. W., Three methods for refining estimates of invariant subspaces, Computing, 38, 43-57 (1987) · Zbl 0602.65022
[19] El Guennouni, A.; Jbilou, K.; Riquet, A., Block Krylov subspace methods for solving large Sylvester equations, Numer. Algorithms, 29, 75-96 (2002) · Zbl 0992.65040
[20] Feitzinger, F.; Hylla, T.; Sachs, E. W., Inexact Kleinman-Newton method for Riccati equations, SIAM J. Matrix Anal. Appl., 31, 272-288 (2009) · Zbl 1191.49033
[21] Flagg, G. M.; Gugercin, S., On the ADI method for the Sylvester equation and the optimal-\(H_2\) points, Appl. Numer. Math., 64, 50-58 (2013) · Zbl 1255.65087
[22] Golub, G.; Van Loan, C., Matrix Computations (2013), Johns Hopkins University Press: Johns Hopkins University Press Baltimore · Zbl 1268.65037
[23] Golub, G. H.; Nash, S.; Van Loan, C. F., A Hessenberg-Schur method for the problem \(AX \times XB = C\), IEEE Trans. Autom. Control, AC-24, 909-913 (1979) · Zbl 0421.65022
[24] Guo, C.; Higham, N., Iterative solution of a nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl., 29, 396-412 (2007) · Zbl 1146.65035
[25] Guo, C.-H., Efficient methods for solving a nonsymmetric algebraic Riccati equation arising in stochastic fluid models, J. Comput. Appl. Math., 192, 353-373 (2006) · Zbl 1102.65049
[26] Guo, C.-H.; Laub, A. J., On the iterative solution of a class of nonsymmetric algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 22, 376-391 (2000) · Zbl 0973.65025
[27] Hewer, G. A., An iterative technique for the computation of steady state gains for the discrete optimal regulator, IEEE Trans. Autom. Control, AC-16, 382-384 (1971)
[30] Jbilou, K., Low rank approximate solutions to large Sylvester matrix equations, Appl. Math. Comput., 177, 365-376 (2006) · Zbl 1095.65041
[31] Juang, J.; Chen, I. D., Iterative solution for a certain class of algebraic matrix Riccati equations arising in transport theory, Transp. Theory Stat. Phys., 22, 65-80 (1993) · Zbl 0774.65020
[32] Kleinman, D., On an iterative technique for Riccati equation computations, IEEE Trans. Autom. Control, AC-13, 114-115 (1968)
[33] Kressner, D.; Tobler, C., Krylov subspace methods for linear systems with tensor product structure, SIAM J. Matrix Anal. Appl., 31, 1688-1714 (2010) · Zbl 1208.65044
[35] Li, T.; Chu, E. K.-w.; Juang, J.; Lin, W.-W., Solution of a nonsymmetric algebraic Riccati equation from a two-dimensional transport model, Linear Algebra Appl., 434, 201-214 (2011) · Zbl 1208.15014
[36] Li, T.; Chu, E. K.-w.; Kuo, Y.; Lin, W.-W., Solving large-scale nonsymmetric algebraic Riccati equations by doubling, SIAM J. Matrix Anal. Appl., 34, 1129-1147 (2013) · Zbl 1286.65055
[37] Mehrmann, V.; Xu, H., Explicit solutions for a Riccati equation from transport theory, SIAM J. Matrix Anal. Appl., 30, 1339-1357 (2009) · Zbl 1176.65055
[42] Sorensen, D.; Zhou, Y., Direct methods for matrix Sylvester and Lyapunov equations, J. Appl. Math, 277-303 (2002) · Zbl 1028.65039
[43] Wachspress, E. L., Iterative solution of the Lyapunov matrix equation, Appl. Math. Lett., 107, 87-90 (1988) · Zbl 0631.65037
[47] Yu, B.; Li, D.-H.; Dong, N., Low memory and low complexity iterative schemes for a nonsymmetric algebraic Riccati equation arising from transport theory, J. Comput. Appl. Math., 250, 175-189 (2013) · Zbl 1285.65024
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.