Solving large-scale continuous-time algebraic Riccati equations (CARE) of the form

\begin{equation} \label {eq:care} A^\top X+XA- XFX+Q=0, \end{equation}

is a significant challenge in various control theory applications. When the numerical range \(\mathcal W(A)\) of \(A\) is in the left part of the complex plane, and \(F,Q\) are low-rank matrices the stabilizing solution \(X\) is numerically low-rank. The latter property can be shown by rewriting (1) as a Sylvester equation with low-rank right-hand side, and by applying singular values inequalities for the solution of this type of equations [1]. In this scenario, one can apply Krylov subspace projection methods or ADI-type methods to efficiently get approximate solutions.

This work is concerned with the non standard large-scale case where the coefficients \(A, F,Q\) are full rank quasiseparable matrices, i.e., all their offdiagonal blocks are low-rank. Within this setting, we provide decay bounds for the singular values of the offdiagonal blocks of \(X\), justifying the approximability of \(X\) by a quasiseparable matrix. To derive these bounds we relate a generic offdiagonal block with the solution of a Sylvester equation with low-rank right-hand side; note that, this can not be trivially obtained by moving the term \(Q-XFX\) to the right-hand side of (1). Our results establish a link between the rate of decay of the offdiagonal singular values and certain rational approximation problems, known as Zolotarev problems, involving the set \(\mathcal W(L^{-1}AL)\), where \(F=LL^\top \) is a Cholesky factorization of \(F\). More explicitly, for a generic offdiagonal submatrix \(M\) of \(X\), we get inequalities of the form

\[ \frac {\sigma _{ht+r}(M)}{||X||_2}\le \kappa \cdot Z_h(W(L^{-1}AL), -W(L^{-1}AL)),\qquad h=1,2,3,\dots , \]

where the shift parameters \(t,r\ge 0\) depend only on the quasiseparable ranks of the coefficients of the CARE, \(\kappa \) is a constant including the condition number of \(F\), and \(Z_h\) indicates the optimal value of the aforementioned Zolotarev problem. When \(W(L^{-1}AL)\subseteq \mathbb C^{-}\), the quantity \(Z_h(W(L^{-1}AL), -W(L^{-1}AL))\) decays rapidly as \(h\) increases.

Quite interestingly, the rank of the offdiagonal submatrices of \(X\) are linked to the tensor train ranks (TT ranks) of the tensor train representation of the value function

\[V(\mathbf y):=\mathbf y^TX\mathbf y\]

associated with the solution of the CARE [3]. As a byproduct of our analysis, we improve and enlarge the scope of existing upper bounds for the numerical TT ranks of \(V(\mathbf y)\) [2, Theorem 3.1].

From the algorithmic view point, we propose two fast Riccati solvers: the first one applies to CAREs with quasiseparable coefficients, and the second one specific to the banded case. The former method exploits the representation of \(A,F,\) and \(Q\), in the hierarhcically semiseparable format (HSS) [7], and is based on a divide-and-conquer scheme, similarly to other recent solvers for matrix equations with hierarchically low-rank coefficients [4, 5]. The method for the banded coefficients case aims at providing a sparse approximation of \(X\), by means of an inexact Newton-Kleinman iteration (NK) combined with a thresholding mechanism that keeps under control the level of sparsity of the iterates. Under reasonable assumptions, both algorithms have at most a linear-logarithmic complexity; when the NK iterate remains sufficiently banded, the second procedure provides a significant speed up thanks to the use of sparse arithmetic.

The content of this talk is based on [6].

References

• [1]  B. Beckermann, and A. Townsend. “Bounds on the singular values of matrices with displacement structure.” SIAM Review 61.2 (2019): 319-344.

• [2]  S. Dolgov, and B. Khoromskij. “Two-level QTT-Tucker format for optimized tensor calculus.” SIAM Journal on Matrix Analysis and Applications 34.2 (2013): 593-623.

• [3]  V. Kazeev, O. Reichmann, and Ch. Schwab. “Low-rank tensor structure of linear diffusion operators in the TT and QTT formats.” Linear Algebra and its Applications 438.11 (2013): 4204-4221.

• [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 (2019): A848-A876.

• [5]  D. Kressner, P. Kürschner, S. Massei. “Low-rank updates and divide-and-conquer methods for quadratic matrix equations”. Numerical Algorithms, 84.2 (2020): 717-741.

• [6]  S. Massei, and L. Saluzzi. “On the data-sparsity of the solution of Riccati equations with applications to feedback control”. arXiv preprint arXiv:2408.16569 (2024).

• [7]  J. Xia, S. Chandrasekaran, M. Gu, and X. Li. “Fast algorithms for hierarchically semiseparable matrices.” Numerical Linear Algebra with Applications 17.6 (2010): 953-976.