Symmetric Eigenproblems

Let ** A** be a real symmetric or
complex Hermitian

The basic task of the symmetric eigenproblem routines is to compute values of
and, optionally, corresponding vectors ** z** for a given matrix

This computation proceeds in the following stages:

- 1.
- The real symmetric or complex Hermitian matrix
is reduced to*A***real tridiagonal form**. If*T*is real symmetric this decomposition is*A*with*A*=*QTQ*^{T}orthogonal and*Q*symmetric tridiagonal. If*T*is complex Hermitian, the decomposition is*A*with*A*=*QTQ*^{H}unitary and*Q*, as before,*T**real*symmetric tridiagonal. - 2.
- Eigenvalues and eigenvectors of the real symmetric tridiagonal matrix
are computed. If all eigenvalues and eigenvectors are computed, this is equivalent to factorizing*T*as , where*T*is orthogonal and is diagonal. The diagonal entries of are the eigenvalues of*S*, which are also the eigenvalues of*T*, and the columns of*A*are the eigenvectors of*S*; the eigenvectors of*T*are the columns of*A*, so that ( when*Z*=*QS*is complex Hermitian).*A*

In the real case, the decomposition ** A = Q T Q^{T}** is computed by one
of the routines xSYTRD, xSPTRD, or xSBTRD,
depending on how the matrix is
stored (see Table 2.10). The complex analogues of these routines
are called xHETRD, xHPTRD, and xHBTRD.
The routine xSYTRD (or xHETRD) represents the
matrix

When packed storage is used, the corresponding routines for forming ** Q**
or multiplying another matrix by

When ** A** is banded and xSBTRD (or xHBTRD)
is used to reduce it to
tridiagonal form,

There are several routines for computing eigenvalues and eigenvectors of ** T**,
to cover the cases of computing some or all of the eigenvalues, and some or
all of the eigenvectors. In addition, some routines run faster in some
computing environments or for some matrices than for others. Also,
some routines are more accurate than other routines.

See section 2.3.4.1 for a discussion.

**xSTEQR**-
This routine uses the implicitly shifted
algorithm. It switches between the*QR*and*QR*variants in order to handle graded matrices more effectively than the simple*QL*variant that is provided by the EISPACK routines IMTQL1 and IMTQL2. See [56] for details. This routine is used by drivers with names ending in -EV and -EVX to compute all the eigenvalues and eigenvectors (see section 2.3.4.1).*QL* **xSTERF**-
This routine uses a square-root free version of the
algorithm, also switching between*QR*and*QR*variants, and can only compute all the eigenvalues. See [56] for details. This routine is used by drivers with names ending in -EV and -EVX to compute all the eigenvalues and no eigenvectors (see section 2.3.4.1).*QL* **xSTEDC**-
This routine uses Cuppen's divide and conquer algorithm
to find the eigenvalues and the eigenvectors (if only eigenvalues
are desired, xSTEDC calls xSTERF). xSTEDC can be many times faster than
xSTEQR for large matrices but needs more work space (
**2**or*n*^{2}**3**). See [20,57,89] and section 3.4.3 for details. This routine is used by drivers with names ending in -EVD to compute all the eigenvalues and eigenvectors (see section 2.3.4.1).*n*^{2} **xSTEGR**-
This routine uses the relatively robust representation (RRR) algorithm to
find eigenvalues and eigenvectors. This routine uses an
factorization of a number of translates*LDL*^{T}of*T*-*sI*, for one shift*T*near each cluster of eigenvalues. For each translate the algorithm computes very accurate eigenpairs for the tiny eigenvalues. xSTEGR is faster than all the other routines except in a few cases, and uses the least workspace. See [35] and section 3.4.3 for details.*s* **xPTEQR**-
This routine applies to symmetric
*positive definite*tridiagonal matrices only. It uses a combination of Cholesky factorization and bidiagonaliteration (see xBDSQR) and may be significantly more accurate than the other routines except xSTEGR. See [14,32,23,51] for details.*QR* **xSTEBZ**-
This routine uses bisection to compute some or all of the
eigenvalues. Options provide for computing all the eigenvalues in a real
interval or all the eigenvalues
from the
to the*i*^{th}largest. It can be highly accurate, but may be adjusted to run faster if lower accuracy is acceptable. This routine is used by drivers with names ending in -EVX.*j*^{th} **xSTEIN**- Given accurate eigenvalues, this routine uses inverse iteration to compute some or all of the eigenvectors. This routine is used by drivers with names ending in -EVX.

See Table 2.10.