Premium
Nonlinear multigrid for the solution of large‐scale Riccati equations in low‐rank and ℋ︁‐matrix format
Author(s) -
Grasedyck L.
Publication year - 2008
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.606
Subject(s) - mathematics , rank (graph theory) , discretization , riccati equation , algebraic riccati equation , multigrid method , matrix (chemical analysis) , nonlinear system , rank condition , partial differential equation , finite element method , mathematical analysis , combinatorics , controllability , materials science , physics , quantum mechanics , composite material , thermodynamics
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.