This section is concerned with the solution of the generalized eigenvalue
problems , , and , where
`A` and `B` are real symmetric or complex Hermitian and `B` is positive definite.
Each of these problems can be reduced to a standard symmetric
eigenvalue problem, using a Cholesky factorization of `B` as either
or ( or in the Hermitian case).
In the case , if `A` and `B` are banded then this may also
be exploited to get a faster algorithm.

With , we have

Hence the eigenvalues of are those of ,
where `C` is the symmetric matrix and .
In the complex case `C` is Hermitian with and .

Table 2.13 summarizes how each of the three types of problem
may be reduced to standard form , and how the eigenvectors `z`
of the original problem may be recovered from the eigenvectors `y` of the
reduced problem. The table applies to real problems; for complex problems,
transposed matrices must be replaced by conjugate-transposes.

**Table 2.13:** Reduction of generalized symmetric definite eigenproblems to standard
problems

Given `A` and a Cholesky factorization of `B`,
the routines xyyGST overwrite `A`
with the matrix `C` of the corresponding standard problem
(see Table 2.14).
This may then be solved using the routines described in
subsection 2.3.4.
No special routines are needed
to recover the eigenvectors `z` of the generalized problem from
the eigenvectors `y` of the standard problem, because these
computations are simple applications of Level 2 or Level 3 BLAS.

If the problem is and the matrices `A` and `B` are banded,
the matrix `C` as defined above is, in general, full.
We can reduce the problem to a banded standard problem by modifying the
definition of `C` thus:

where `Q` is an orthogonal matrix chosen to ensure that `C` has bandwidth
no greater than that of `A`.
`Q` is determined as a product of Givens rotations.
This is known as Crawford's algorithm
(see Crawford [14]).
If `X` is required, it must be formed explicitly by the reduction routine.

A further refinement is possible when `A` and `B` are banded, which halves
the amount of work required to form `C` (see Wilkinson [79]).
Instead of the standard Cholesky factorization of `B` as or ,
we use a ``split Cholesky'' factorization
( if `B` is complex), where:

with upper triangular and lower triangular of
order approximately `n` / 2;
`S` has the same bandwidth as `B`. After `B` has been factorized in this way
by the routine
xPBSTF ,
the reduction of the banded generalized
problem to a banded standard problem
is performed by the routine xSBGST
(or xHBGST for complex matrices).
This routine implements a vectorizable form of the algorithm, suggested by
Kaufman [57].

-------------------------------------------------------------------- Type of matrix Single precision Double precision and storage scheme Operation real complex real complex -------------------------------------------------------------------- symmetric/Hermitian reduction SSYGST CHEGST DSYGST ZHEGST -------------------------------------------------------------------- symmetric/Hermitian reduction SSPGST CHPGST DSPGST ZHPGST (packed storage) -------------------------------------------------------------------- symmetric/Hermitian split SPBSTF CPBSTF DPBSTF ZPBSTF banded Cholesky factorization -------------------------------------------------------------------- reduction SSBGST DSBGST CHBGST ZHBGST --------------------------------------------------------------------

Tue Nov 29 14:03:33 EST 1994