next up previous contents index
Next: Transformation to Standard Problem Up: Introduction Previous: Eigenvalues Sought.   Contents   Index

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

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

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.


next up previous contents index
Next: Transformation to Standard Problem Up: Introduction Previous: Eigenvalues Sought.   Contents   Index
Susan Blackford 2000-11-20