Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.
MiS Preprint
84/2005
Nonlinear multigrid for the solution of large scale Riccati equations in low-rank and $\cal H$-matrix format
Lars Grasedyck
Abstract
The algebraic matrix Riccati equation $AX + XA^{T} - XFX + C = 0$, where the matrices $A,B,C,F\in\mathbb{R}^{n\times n}$ are given and a solution $X\in\mathbb{R}^{n\times n}$ is sought, plays a fundamental role in optimal control problems. Large scale systems typically appear if the constraint is described by a partial differential equation. We provide a nonlinear multigrid algorithm that computes the solution $X$ in a data-sparse low rank format and has a complexity of ${\cal O}(n)$, provided that $F$ and $C$ are of low rank and $A$ is the Finite Element or Finite Difference discretisation of an elliptic PDE.
We indicate how to generalise the method to $\cal H$-matrices $C,F$ and $X$ that are only blockwise of low rank and thus allow a broader applicability with a complexity of ${\cal O}(n\log(n)^c)$. The method can as well be applied for unstructured and dense matrices $C$ and $X$ in order to solve the Riccati equation in ${\cal O}(n^2)$.
