Sparse grid approximation of the Riccati equation

In this article, we study the sparse grid discretization for the numerical solution of the algebraic Riccati equation (ARE). This approach is of particular interest for the solution of large scale AREs. Such AREs arise, for example, from the discretization of the operator Riccati equations associated with the linear quadratic control of systems evolving in a Hilbert space $H$. Following [4, 45], we formulate the ARE as a nonlinear operator equation on the space of Hilbert–Schmidt operators and derive the matrix equation for the sparse grid discretization. Provided that $O(N)$ degrees of freedom are used to discretize the space $H$, the sparse grid approximation of the ARE requires $O(N \log N)$ degrees of freedom. Especially, we propose an algorithm that evaluates the approximated ARE with $O(N^{3/2})$ operations. This considerably reduces the cost of solving the ARE compared to the $O(N^2)$ memory requirement and $O(N^3)$ complexity of the regular tensor product discretization. Numerical results are presented to validate the approach.