Specifying a Singular Value Problem

The following problems are typical, both because they arise naturally in applications and because we have good algorithms for them. They correspond to the problems in §2.2.6.

1. Compute all the singular values to some specified accuracy.
2. Compute singular values $\sigma_i$ for some specified set of subscripts $i \in {\cal I} = \{1,2,\ldots,n\}$, including the special cases of the smallest $r$ singular values $\sigma_{n-r+1}$ through $\sigma_n$, and the largest $r$ singular values $\sigma_1$ through $\sigma_r$. Again, the desired accuracy may be specified.
3. Compute all the singular values within a given subset of the real axis, such as the interval $[\alpha, \beta]$. Again, the desired accuracy may be specified.
4. Count all the singular values in the interval $[\alpha, \beta]$. This does not require computing the singular values in $[\alpha, \beta]$, and so can be much cheaper.
5. Compute a certain number of singular values closest to a given value $\mu$.

For each of these possibilities (except 4) the user can also compute the corresponding singular vectors (left, right, or both). For the singular values that are clustered together, the user may choose to compute the associated singular subspace(s), since in this case the individual singular vectors can be very ill-conditioned, while the singular subspace(s) may be less so. Finally, for any of these quantities, the user might also want to compute its condition number.

Even though we have effective algorithms for these problems, we cannot necessarily achieve them all for large scale problems in an amount of time and space acceptable to all users.