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

Lars Grasedyck

Contact the author: Please use for correspondence this email.
Submission date: 19. Sep. 2005 (revised version: May 2007)
Pages: 32
published in: Numerical linear algebra with applications, 15 (2008) 9, p. 779-807 
DOI number (of the published article): 10.1002/nla.606
Bibtex
MSC-Numbers: 65F05, 65F30, 65F50
Keywords and phrases: data-sparse approximation, riccati equation, low rank approximation, multigrid method, hierarchical matrices
Download full preprint: PDF (341 kB)

Abstract:
The algebraic matrix Riccati equation , where the matrices are given and a solution 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 , 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 -matrices C,F and X that are only blockwise of low rank and thus allow a broader applicability with a complexity of . The method can as well be applied for unstructured and dense matrices C and X in order to solve the Riccati equation in .