Efficient iterative methods for the solution of Generalized Lyapunov Equations: Block vs. point Krylov projections, and other controversial decisions

Data Seminario: 
04-Mar-2020
Ora Inizio: 
11:00
Ora Fine: 
12:00
Daniel Szyld
Temple University

There has been a flurry of activity in recent years in the area of solution of matrix equations. In par-
ticular, a good understanding has been reached on how to approach the solution of large scale Lya-
punov equations. An effective way to solve Lyapunov equations of the form $A^T X + XA + C^TT C = 0$,
where A and X are n×n, is to use Galerkin projection with appropriate extended or rational Krylov
subspaces. These methods work in part because the solution is known to be symmetric positive
definite with rapidly decreasing singular values, and therefore it can be approximated by a low
rank matrix X_k = Z_k Z_k^T. Thus the computations are performed usually with storage which is
lower rank, i.e., much lower than order of n^2 .

Generalized Lyapunov equations have additional terms. In this talk, we concentrate on equations
of the following form
$$
A^T X + XA + \sum_{j = 1}^m N_j X N_j^T + C^T C = 0,
$$
Such equations arise for example in stochastic control.
In the present work, we propose a return to classical iterative methods, and consider instead stationary iterations. The classical theory of splittings applies here, and we present a new theoremon the convervegence when the linear system at each step is solved inexactly.

Several theoretical and computational issues are discussed so as to make the iteration efficient.
Numerical experiments indicate that this method is competitive vis-à-vis the current state-of-the-
art methods, both in terms of computational times and storage needs.

This is joint work with Stephen D. Shank and Valeria Simoncini.