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

$$B=LL^{\ast},$$ (69)

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

$$Cy=\lambda y,$$ (70)

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

$$x=L^{-\ast}y\,.$$

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

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

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

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

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

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

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

$$C=(A-\sigma B)^{-1}B\,.$$

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

$$\lambda=\sigma+\frac{1}{\theta},$$

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.