Overview of Available Algorithms.

When $A$ is not too large, so that it can be stored and manipulated as a dense $m$ by $n$ matrix, there are transformation methods that compute the SVD of $A$. These algorithms are available in LAPACK [12], ScaLAPACK [52], and MATLAB, and are discussed in §6.2.

The main emphasis in this book is on iterative methods, where $A$ is stored and operated on sparsely. The iterative methods for the Hermitian eigenvalue problem discussed in Chapter 4 can be applied to one of the three Hermitian matrices $AA^*$, $A^* A$, or $H(A)$ discussed above. Rather than repeat this material, we will discuss the pros and cons of the different methods from Chapter 4, depending on which singular values and vectors one wants to compute, whether one chooses $AA^*$, $A^* A$, or $H(A)$, the distribution of the singular values of $A$, the sparsity structure of $A$, whether one uses shift-and-invert, etc.

To this end, we note that for the task such as counting the number of singular values of $A$ that are in a given interval $[\alpha, \beta]$, it does not require computing the singular values and so can be much cheaper. The key tool is the matrix inertia as presented in §4.1 (p. ). It can be extended easily to apply to one of the Hermitian matrices $AA^*$, $A^* A$, or $H(A)$.