Speaker
Description
The numerical solution of the algebraic Riccati matrix equation
$$(1)\quad A^T X + XA − XSX + Q = 0,$$
where $A$, $S$, $Q\in\mathbb{R}^{n\times n}$ , is an interesting and still challenging task especially when the problem dimension is very large, say $n > 10^4$ , as the dense solution $X$ cannot be store and a memory-saving approximation has to be sought.
A vast portion of the literature focuses on the case of low-rank $S$ and $Q$ and many, diverse solution schemes have been developed to tackle this kind of equations. See, e.g., [1] and the references therein. In particular, the so-called low-rank methods compute a low-rank approximation to the exact solution $X$ in order to moderate the memory requirements of the adopted algorithm.
By exploiting novel results about the solution of Lyapunov equations with non low-rank right-hand side [2,3], a Newton iteration for (1) with a rank-structured $Q$ has been recently proposed [4]. However, also in such a scheme the matrix $S$ is still supposed to be low-rank.
In this talk we consider Riccati equations with banded, full-rank coefficent matrices $A$, $S$ and $Q$ and, by taking inspiration from some early results by Incertis [5], a fresh solution procedure that efficiently computes memory-saving approximate solutions is proposed. In particular, the structure of the computed solution $\tilde X$ depends on some properties of the matrices $A$ and $Q$ and we can represent $\tilde X$ in terms of either a banded matrix or a banded plus low-rank matrix maintaining a very low storage demand of the overall solution process.
Several numerical results are reported to illustrate the potential of the discussed method.
References
[1] P. Benner, Z. Bujanovic, P. Kürschner and J. Saak. A numerical comparison of solvers for large-scale, continuous-time algebraic Riccati equations. ArXiv Preprint: 1811.00850, 2018.
[2] D. Palitta and V. Simoncini. Numerical methods for large-scale Lyapunov equations with symmetric banded data. SIAM Journal on Scientific Computing, 40 (5): A3581–A3608, 2018.
[3] S. Massei, D. Palitta and L. Robol. Solving rank structured Sylvester and Lyapunov equations. SIAM Journal on Matrix Analysis and Applications, 39 (4): 1564–1590, 2018.
[4] D. Kressner, S. Massei and L. Robol. Low-rank updates and a divide-and-conquer method for linear matrix equations. SIAM Journal on Scientific Computing, 41 (2): A848–A876, 2019.
[5] F. C. Incertis. A new formulation of the algebraic Riccati equation problem. IEEE Transactions on Automatic Control, 26 (3): 768–770, 1981.
