Document ID sheet  Systems and Control Engineering at ULg
 TITLE: Invariant Subspace Computation: A Geometric Approach
 AUTHOR: P.A. Absil
 ABSTRACT:

We propose two generalized versions of the wellknown Rayleigh
quotient iteration (RQI). The generalized iterations are proven to
generate welldefined iterations on the Grassmann manifold of
pplanes in R^n, and to converge locally cubically to the
spectral (i.e. isolated) eigenspaces of a symmetric matrix A.
One of the iterations (GRQI) uses a matrix Rayleighquotient shift
in a Sylvester equation. The other iteration (RSQR) involves a
succession of scalar shifts. The practical implementation of both
methods is studied. A dynamical systems approach of the behaviour
of GRQI is sketched.
Related paper: A GrassmannRayleigh quotient iteration for computing invariant subspaces.

A twosided version of GRQI is proposed. Its iterates are
pairs of pdimensional subspaces of R^n and it converges
locally cubically to the pairs of leftright nondefective spectral
eigenspaces of arbitrary square matrices. The iteration is
particularized to structured eigenproblems, including the
Hamiltonian eigenproblem and the symmetric generalized
eigenproblem.
Related paper: Twosided Rayleigh quotient iteration.

Using the representation of pdimensional subspaces of
R^n by nbyp matrices that span the subspace, we derive
formulas for essential differentialgeometric objects on the
Grassmann manifold, including the O_ninvariant metric and the
associated Riemannian connection and geodesics. These formulas
allow us to particularize to the Grassmann manifold the
RiemannNewton method proposed by S. T. Smith. This
GrassmannNewton method can be utilized for solving problems that
are expressed as a zerofinding problem on the Grassmann manifold.
We show how eigenspace computation can be formulated in such a way
for arbitrary A, and we derive the corresponding Newton
iteration. This gives us insight to propose two other Newtonlike
methods for eigenspace computation. The convergence is quadratic
in general, and cubic if and only if the target eigenspace is also
a lefteigenspace.
Related paper: Riemannian geometry of Grassmann manifolds with a view on algorithmic computation.

We propose ways to enlarge the basins of attraction of
eigenspaces under the proposed iterations. In the GRQI case, a
simple threshold applied on the distance between two successive
iterates is shown to considerably improve the quality of the
basins of attraction. In the Newton case, since our numerical
experiments suggest that a steepest descent flow of a residual
function possesses excellent global convergence properties, we
design a continuous deformation between the Newton step and the
steepest descent approach. We propose a simple way to select the
deformation parameter in the course of the iteration so as to
benefit from the global convergence properties of the gradient
descent flow while preserving the cubic convergence rate of the
pure Newton method.
Related paper: Cubically convergent iterations for invariant subspace computation.
 STATUS: PhD thesis. Submitted to the ``Faculté des Sciences
Appliquées de l'Université de Liège'', 10 December
2002. The PhD defense took place at the University of Liege on 13
February 2003.
 DATE OF ENTRY: February 2003.
[Home]