Calculation of Invariant Subspaces of Large and Sparse Matrices.

Jan Brandts

Mathematics Institute, Utrecht University, Budapestlaan 6, 3584 CD Utrecht, Netherlands.


Abstract

Eigendata calculations for large and sparse matrices are mostly done by Ritz-Galerkin projection of the large problem onto a small subspace. This happens for example in the Power Method (on a one-dimensional subspace), in Subspace Iteration and Block Rayleigh Quotient Iteration (on a subspace of a fixed dimension p), the Lanczos and the Arnoldi methods, and also in the Jacobi-Davidson method (on subspaces of variable dimensions).

In methods in which the subspace is changed or expanded, the question of how to do that is a very important one. The ideal change is given by the solution of a generalized algebraic Riccati equation, which would yield an invariant subspace immediately. This Riccati equation, however, is as hard to solve as the original problem.

In this presentation we will show the consequences of solving the Riccati equation by iterative methods, and using the iterates as new subspace vectors, or as vectors with which to expand a given subspace. This will lead to an improvement of Inexact Block Rayleigh Quotient Iteration, and also to new algorithms for invariant subspaces that are block versions (or variations of those) of the Jacobi-Davidson Method.

We stress that the algorithms for the Riccati equation can be of interest in other areas of research as well, such as control theory, and in solving the Ricatti differential equations.

Keywords: Riccati equation, Ritz-Galerkin method, Sylvester equation, stability of invariant subspaces, Block Jacobi-Davidson method.