next up previous contents index
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 $B$ or $A$ 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

\begin{displaymath}
B=LL^{\ast},
\end{displaymath} (69)

e.g., using Cholesky decomposition, and apply a standard Hermitian algorithm to
\begin{displaymath}
Cy=\lambda y,
\end{displaymath} (70)

where $C=L^{-1}AL^{-\ast}$. The eigenvectors $x$ of the original pencil (5.1) can be recovered by a back substitution,

\begin{displaymath}x=L^{-\ast}y\,.\end{displaymath}

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

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

\begin{displaymath}y=Cx=L^{-1}(A(L^{-\ast}x)),\end{displaymath}

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

\begin{displaymath}
(C-\sigma I)^{-1}
= (L^{-1}AL^{-\ast}-\sigma I)^{-1}
= L^{\ast}(A-\sigma B)^{-1}L,
\end{displaymath}

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

\begin{displaymath}y=(C-\sigma I)^{-1}x=L^{\ast}(R^{-1}(D^{-1}(R^{-\ast}(Lx))))\end{displaymath}

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 $A-\sigma B$ and applying the extra operations on triangular matrices.

It looks like a shift-and-invert algorithm needs two matrix factorizations, one of $B$ (5.4) and one of $A-\sigma B$ (5.6), but we may avoid factoring $B$ 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 $B$ is to apply any algorithm for non-Hermitian matrices, described in Chapter 7, to the non-Hermitian matrix

\begin{displaymath}C=(A-\sigma B)^{-1}B\,.\end{displaymath}

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

\begin{displaymath}
\lambda=\sigma+\frac{1}{\theta},
\end{displaymath}

where $\theta $ are the eigenvalues of $C$. 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 $C$ will have a reasonably well-conditioned eigenproblem, provided that $B$ 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 up previous contents index
Next: Direct Methods Up: Generalized Hermitian Eigenvalue Problems Previous: Storage and Work.   Contents   Index
Susan Blackford 2000-11-20