XYeupd

The purpose of XYeupd  is to obtain the requested eigenvalues and eigenvectors (or Schur basis vectors) for the original problem from the information computed by XYaupd for the linear operator .Regardless of whether a spectral transformation is used, the eigenvectors will remain unchanged on transforming back to the original problem. If a spectral transformation is used, then subroutine XYaupd will compute eigenvalues of Subroutine XYeupd maps them to those of except in two cases. The exceptions occur when using [s,d]naupd with a complex shift with either of or Note that if is a real shift, [s,d]neupd can recover the eigenvalues since then Otherwise, the eigenvalues must be recovered by the user, preferably by using the converged Ritz vectors and computing Rayleigh quotients with them for the original problem. We hope to automate this step in a future release.

If eigenvectors are desired, an orthonormal basis for the invariant subspace corresponding to the converged Ritz values is first computed. The vectors of this orthonormal basis are called approximate Schur vectors for Figure 5.2 outlines our strategy. Refer to Figure 5.2 for definitions of the quantities discussed in the remainder of this section.

  

Figure 5.2: Outline of algorithm used by subroutine XYeupd to compute Schur vectors and possibly eigenvectors.

Compute the partial Schur form ${\bf H}_m {\bf Q}_k = {\bf Q}_k {\bf R}_k,$ where the $k$ converged, wanted Ritz values computed by XYaupd are located on the diagonal of the upper triangular matrix ${\bf R}_k$ of order $k.$ Compute the approximate Schur vectors of $\bf A$ by forming ${\bf V}_m {\bf Q}_k$ and placing in the first $k$ columns of ${\bf V}_m.$ Denote the matrix consisting of these first $k$ columns by ${\bf V}_k.$ If eigenvectors are desired, then Compute the eigendecomposition ${\bf R}_k {\bf S}_k = {\bf S}_k {\bf D}_k.$ Compute the Ritz vectors by forming ${\bf V}_k {\bf S}_k.$

For symmetric eigenvalue problems [s,d]seupd does not need Step 3 of Figure 5.2 since Schur vectors are also eigenvectors. Moreover, a special routine is not required to re-order the Schur form since is a diagonal matrix of real eigenvalues.

For real non-symmetric eigenvalue problems, [s,d]neupd uses the real Schur form. That is, is an upper quasi-triangular matrix with 1-by-1 and 2-by-2 diagonal blocks; each 2-by-2 diagonal block has its diagonal elements equal and its off-diagonal elements of opposite sign. Associated with each 2-by-2 diagonal block is a complex conjugate pair of eigenvalues. The real eigenvalues are stored on the diagonal of Similarly, is a block diagonal matrix. When the eigenvalue is complex, the complex eigenvector associated with the eigenvalue with positive imaginary part is stored in two consecutive columns of The first column holds the real part of the eigenvector and the second column holds the imaginary part. The eigenvector associated with the eigenvalue with negative imaginary part is simply the complex conjugate of the eigenvector associated with the positive imaginary part. The computed Ritz vectors are stored in the same manner.

The computation of the partial Schur form needed at Step 1 is performed by first calling the appropriate LAPACK subroutine that computes the full Schur decomposition of Another LAPACK subroutine, Xtrsen , re-orders the computed Schur form to obtain and The approximate Schur vectors are formed by computing the QR factorization of and then postmultiplying with the factored form. This avoids the need for the additional storage that would be necessary if were computed directly. The appropriate LAPACK subroutines are used to compute and apply the QR factorization of The factored approach described above is extremely stable and efficient since is a numerically orthogonal matrix.

In exact arithmetic, there would be no need to perform the reordering (or the sorting for the symmetric eigenvalue problem). In theory, the implicit restarting mechanism would obviate the need for this. However, computing in finite precision arithmetic (as usual) complicates the issue and make these final reorderings mandatory. See Chapter 5 in [22] and [26] for further information.

When Ritz vectors are required, the LAPACK subroutine Xtrevc  is called to compute the decomposition Since is an upper quasi triangular matrix, the product is easily formed using the level 3 BLAS subroutine Xtrmm .

The computed eigenvectors (Ritz vectors) returned by XYeupd are normalized   to have unit length with respect to the semi-inner product that was used. Thus, if they will have unit length in the standard 2-norm. In general, a computed eigenvector will satisfy with respect to the matrix that was specified.