Generalized Symmetric Definite Eigenproblems     Next: Generalized Nonsymmetric Eigenproblems Up: Computational Routines Previous: Singular Value Decomposition

Generalized Symmetric Definite Eigenproblems

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 ). 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 ). 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 .

--------------------------------------------------------------------
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
--------------------------------------------------------------------

Table 2.14: Computational routines for the generalized symmetric definite eigenproblem     Next: Generalized Nonsymmetric Eigenproblems Up: Computational Routines Previous: Singular Value Decomposition

Tue Nov 29 14:03:33 EST 1994