Self-adjoint Eigenproblems

next up previous
Next: Non-self-adjoint Eigenproblems Up: Desired Spectral Information Previous: Desired Spectral Information

Self-adjoint Eigenproblems

We first consider the -by- Hermitian matrix , which has real eigenvalues . When computing eigenvalues, the following choices are possible:

  1. All the eigenvalues, to some specified accuracy.
  2. Eigenvalues for some specified set of subscripts , including the special cases of the largest eigenvalues through , and the smallest eigenvalues through . Again, the desired accuracy may be specified.
  3. All the eigenvalues within a given subset of the real axis, such as the interval . Again, the desired accuracy may be specified.

  4. Certain number of eigenvalues closest to a given value .

For each of these possibilities, the user can also compute the corresponding eigenvectors (in this case left and right eigenvectors are equal). For the eigenvalues that are clustered together, the user may choose to compute the associated invariant subspace, i.e. the space spanned by the corresponding eigenvectors, since in this case the individual eigenvectors can be very ill-conditioned, while the invariant subspace may be less so.

The spectral information one can request from a singular value decomposition is similar, except that there are left and right singular vectors and singular subspaces, corresponding to eigenvectors and invariant subspaces. Common requests might include the numerical rank, the null space, and the range space. In order to compute these the user must supply a tolerance , which will determine which singular values are considered to be nonzero or zero. Methods can differ greatly depending on whether there is a gap between the singular values larger than and those smaller, and whether the user wants an approximate or precise answer.

Self-adjoint matrix pencils , where and are -by- and Hermitian, and can be simultaneously diagonalized by a congruence, are quite similar. The case corresponds to the standard Hermitian eigenproblem just discussed. has real eigenvalues which we denote . If is nonsingular, . The user may request similar subsets of eigenvalues as described above, as well as right and/or left eigenvectors. If the pencil is non-singular, the user may request right or left deflating subspaces, which are generalizations of invariant subspaces [37]. If is a singular pencil, the common null-space of and can also be computed, as well as the deflating subspaces of the regular part.

Just as the SVD of A is closely related to the eigendecomposition of , the QSVD corresponds to the matrix pencil . The case corresponds to the usual SVD.

Table 2 spells out the possible decompositions which display all the information the user could want. We use terminology which will apply to the non-Hermitian problem too. ``Schur'' form refers to the simplest decomposition possible with complex unitary transformations. (Real orthogonal matrices are also possible, if the original data is real; we leave out the real case for ease of exposition.) ``Jordan-Schur'' form refers to the most detailed decomposition possible with unitary transformations; this form reduces the matrix or matrices to ``staircase'' form [41], wherein all the sizes of Jordan blocks are immediately available, and some more detailed invariant (or deflating [37] or reducing [42]) subspaces are computed. ``Jordan'' form, which typically requires non-unitary transformations and so can be very ill-conditioned to compute, is the most detailed decomposition. Jordan form is usually called Weierstrass form for regular pencils, and Kronecker form for singular pencils. and matrices in the table are unitary, matrices are general nonsingular, is real and diagonal, is real, diagonal, and nonnegative, matrices are upper triangular, and matrices are in upper triangular staircase form.

The decompositions may also be written with and isolated on the left-hand-side, for example instead of . The reason for writing these decompositions as they are shown, is that they can be partial decompositions, if only of the eigenvalues or singular values are of interest to the user. In this case the central matrices (, , , , , , , and ) will be -by-, and the outer matrices (, and ) will be -by-.

Table 2: The Possible ``Eigendecompositions'' of Self-adjoint Eigenproblems

In addition to these decompositions, the user may request condition numbers for any of the computed quantities (eigenvalues, means of eigenvalue clusters, eigenvectors, invariant/deflating/reducing subspaces) [13][38][27]. Given computed values for eigenvalues, eigenvectors, and/or subspaces, the user may also request an a posteriori error bound based on a computed residual.

next up previous
Next: Non-self-adjoint Eigenproblems Up: Desired Spectral Information Previous: Desired Spectral Information

Jack Dongarra
Wed Jun 21 02:35:11 EDT 1995