Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices

Lars Grasedyck, Wolfgang Hackbusch, and Boris N. Khoromskij

Contact the author: Please use for correspondence this email.
Submission date: 30. Jul. 2002
Pages: 36
published in: Computing, 70 (2003) 2, p. 121-165 
DOI number (of the published article): 10.1007/s00607-002-1470-0
Bibtex
MSC-Numbers: 65F05, 65F30, 65F50
Keywords and phrases: hierarchical matrices, riccati equation, lyapunov equation
Download full preprint: PDF (583 kB), PS ziped (593 kB)

Abstract:
In previous papers, a class of hierarchical matrices (H-matrices) is introduced which are data-sparse and allow an approximate matrix arithmetic of almost optimal complexity. Here, we investigate a new approach to exploit the H-matrix structure for the solution of large scale Lyapunov and Riccati equations as they typically arise for optimal control problems where the constraint is a partial differential equation of elliptic type. This approach leads to an algorithm of linear-logarithmic complexity in the size of the matrices.