Search

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 (www.arxiv.org) 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
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)$.

Received:
Sep 19, 2005
Published:
Sep 19, 2005
MSC Codes:
65F05, 65F30, 65F50
Keywords:
data-sparse approximation, riccati equation, low rank approximation, multigrid method, hierarchical matrices

Related publications

inJournal
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