Storage and Work.

In the final columns of Table 5.1, we give an estimate of storage needed and extra work for factorizations.

``#vec''

gives how many vectors one needs to store. The meaning of 2 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. ``$LL^{\ast}$'' means a sparse Cholesky factorization, ``$LDL^{\ast}$,'' a sparse symmetric indefinite Gaussian elimination, and ``ILU'' is an incomplete factorization. It is supposed to be more compact and need less arithmetic work than the other two.

We note that a task such as counting the number of eigenvalues of $A - \lambda B$ that are smaller than a given real number $\alpha$ or are in a given interval $[\alpha, \beta]$ does not require computing the eigenvalues, 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 the case of $A - \lambda B$ assuming $B$ positive definite. In summary, let

$$A - \alpha B = L_{\alpha} D_{\alpha} L^T_{\alpha}, \quad A - \beta B = L_{\beta} D_{\beta} L^T_{\beta}$$

be the LDL$^{T}$ factorizations of matrices $A - \alpha B$ and $A - \beta B$, respectively, where we assume that $D_{\alpha}$ and $D_{\beta}$ are nonsingular diagonal matrices. We refer to §10.3 for the information on software availability for the LDL$^{T}$ factorization. Then the number of eigenvalues of $A - \lambda B$ in $[\alpha, \beta]$ equals $\nu(D_{\beta}) - \nu(D_{\alpha})$, where $\nu(D)$ denotes the number of negative diagonal elements.