Storage.

In the final columns of Table 4.1, we give an estimate of the storage needed.

``#vec''

gives how many vectors one needs to store. The meaning of 2 or 3 is obvious; ``Moderate'' means a multiple of the number $m$ of eigenvalues sought, say $3m$ to $5m$. ``Few'' is smaller than moderate, say $m+10$, and ``Many'' is larger.

``Fact''

indicates whether we need extra matrix storage. ``LU'' means a sparse LU factorization, ``ILU,'' an incomplete factorization. This is supposed to be more compact than LU decomposition.

To this end, we note that tasks such as counting the number of eigenvalues of $A$ that are smaller than a given real number $\alpha$ or are in a given interval $[\alpha, \beta]$ do not require computing the eigenvalues and so can be performed much more cheaply. The key tool is the matrix inertia. The inertia of $A$ is the triplet of integers $(\nu(A),\zeta(A),\pi(A))$, where $\nu(A)$ is the number of negative eigenvalues of $A$, $\zeta(A)$ is the number of zero eigenvalues of $A$, and $\pi(A)$ is the number of positive eigenvalues of $A$. Sylvester's law of inertia states that the inertia of a matrix is invariant under congruence; that is, for all nonsingular matrices $F$, $A$, and $F^T A F$ have the same inertia. See, for examples, [198, p. 403] or [114, p. 202].

Suppose that the shifted matrix $A - \alpha I$ has the LDL$^{T}$ factorization

$$A - \alpha I = L D L^T,$$

where $D$ is a diagonal matrix. Then by Sylvester's law of inertia, $\nu(A - \alpha I) = \nu(D)$. Therefore, the number of negative diagonal elements in $D$ from the LDL$^{T}$ factorization of $A - \alpha I$ gives the number of eigenvalues of $A$ smaller than $\alpha$. In the engineering literature, $\nu(A-\alpha I)$ is often called the Sturm sequence number.

It is easy to see that $\nu(A - \beta I) - \nu(A - \alpha I)$ is the number of eigenvalues in the interval $[\alpha, \beta]$, assuming that $\alpha < \beta$ and the two shifted matrices $A - \alpha I$ and $A - \beta I$ are nonsingular. Thus, the cost of counting the number of eigenvalues of $A$ in a given interval $[\alpha, \beta]$ is equivalent to the cost of two LDL$^{T}$ factorizations of $A - \alpha I$ and $A - \beta I$, respectively. This is much cheaper than finding all eigenvalues in $[\alpha, \beta]$. We refer to §10.3 for the software availability of the LDL$^{T}$ factorization.

In practice, the counting technique is frequently used as a verification tool for the so-called trust interval of a numerical method for finding all eigenvalues in a given interval $[\alpha, \beta]$.