Next: Direct Methods Up: Generalized Hermitian Eigenvalue Problems Previous: Storage and Work.   Contents   Index

# Transformation to Standard Problem

We can reformulate the GHEP (5.1) into a standard eigenvalue problem if we can factor either or or a linear combination of these matrices. See §10.3 for a brief survey of matrix factorizations.

In the former case we make the decomposition

 (69)

e.g., using Cholesky decomposition, and apply a standard Hermitian algorithm to
 (70)

where . The eigenvectors of the original pencil (5.1) can be recovered by a back substitution,

This strategy is advisable whenever the matrix is reasonably well conditioned with respect to inversion or when it has a simpler structure than , as when is diagonal.

The matrix is Hermitian, and we may apply any of the iteration algorithms described in Chapter 4. Each time the matrix is applied to a vector, the computations are made in the order indicated by the parentheses in the expression

that is, a back substitution, followed by a matrix-vector multiply and a forward substitution.

We may also apply a shift-and-invert spectral transformation (SI) from Chapter 4, noting that

and using a symmetric indefinite factorization, in general, A-B=R^DR with block-diagonal to compute

in the order indicated by the parentheses.

As in the standard case, this shift-and-invert variant most often converges in fewer steps, compensating for the cost of factorizing the shifted matrix and applying the extra operations on triangular matrices.

It looks like a shift-and-invert algorithm needs two matrix factorizations, one of (5.4) and one of (5.6), but we may avoid factoring if we use any of the algorithms developed specially for generalized eigenproblems (5.1), which are described later in this chapter.

Another way to avoid factorizing is to apply any algorithm for non-Hermitian matrices, described in Chapter 7, to the non-Hermitian matrix

The eigenvalues of the original pencil (5.1) can be computed as

where are the eigenvalues of . It has the same eigenvectors as the original pencil (5.1).

The main advantage of this second approach is that we may have a standard non-Hermitian code, such as the implicitly restarted Arnoldi method (see §7.6), easily available. The nonsymmetric matrix will have a reasonably well-conditioned eigenproblem, provided that is well-conditioned with respect to inversion, but there is still a risk that we get a solution that violates some of the properties of a GHEP. For example, we may get eigenvalues with small but nonzero imaginary parts.

Next: Direct Methods Up: Generalized Hermitian Eigenvalue Problems Previous: Storage and Work.   Contents   Index
Susan Blackford 2000-11-20