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

The algebraic matrix Riccati equation AX + XA T − XFX + C =0, where matrices A, B, C, F  ∈ ℝ n × n are given and a solution X  ∈ ℝ n × 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 (PDE). We provide a nonlinear multigrid algorithm that computes the solution X in a data‐sparse, low‐rank format and has a complexity of ( n ), subject to the condition that F and C are of low rank and A is the finite element or finite difference discretization of an elliptic PDE. We indicate how to generalize 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 ( n log( n ) p ), p being a small constant. The method can also be applied to unstructured and dense matrices C and X in order to solve the Riccati equation in ( n 2 ). Copyright © 2008 John Wiley & Sons, Ltd.