MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV ( that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint

Nonlinear multigrid for the solution of large scale Riccati equations in low-rank and $\cal H$-matrix format

Lars Grasedyck


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)$.

MSC Codes:
65F05, 65F30, 65F50
data-sparse approximation, riccati equation, low rank approximation, multigrid method, hierarchical matrices

Related publications

2008 Repository Open Access
Lars Grasedyck

Nonlinear multigrid for the solution of large scale Riccati equations in low-rank and \(\mathscr {H}\)-matrix format

In: Numerical linear algebra with applications, 15 (2008) 9, pp. 779-807