Document ID sheet - Systems and Control Engineering at ULg
- TITLE: Invariant Subspace Computation: A Geometric Approach
- AUTHOR: P.-A. Absil
We propose two generalized versions of the well-known Rayleigh
quotient iteration (RQI). The generalized iterations are proven to
generate well-defined iterations on the Grassmann manifold of
p-planes 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 Rayleigh-quotient 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 Grassmann-Rayleigh quotient iteration for computing invariant subspaces.
A two-sided version of GRQI is proposed. Its iterates are
pairs of p-dimensional subspaces of R^n and it converges
locally cubically to the pairs of left-right nondefective spectral
eigenspaces of arbitrary square matrices. The iteration is
particularized to structured eigenproblems, including the
Hamiltonian eigenproblem and the symmetric generalized
Related paper: Two-sided Rayleigh quotient iteration.
Using the representation of p-dimensional subspaces of
R^n by n-by-p matrices that span the subspace, we derive
formulas for essential differential-geometric objects on the
Grassmann manifold, including the O_n-invariant metric and the
associated Riemannian connection and geodesics. These formulas
allow us to particularize to the Grassmann manifold the
Riemann-Newton method proposed by S. T. Smith. This
Grassmann-Newton method can be utilized for solving problems that
are expressed as a zero-finding 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 Newton-like
methods for eigenspace computation. The convergence is quadratic
in general, and cubic if and only if the target eigenspace is also
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
- DATE OF ENTRY: February 2003.