HP MLIB User's Guide Vol. 2 7th Ed.

Chapter 15 Sparse Eigenvalues and Eigenvectors 1009
What you need to know to use these subprograms
an interval specification [a,b] that lies to one side of zero (for example,
[1.0,100.0], [−9.99,−1.0] or [0.0, 25.0], but not [−100.0,100.0]). This restriction
on the interval does not apply to the other descriptors (all, lowest, or nearest).
When you want the algebraically least or greatest eigenvalues, the problem
must be transformed into finding the eigenvalues nearest one or the other
endpoint of the interval.
Trust regions and matrix inertias (Sturm sequence counts)
This sparse eigenanalysis package includes an independent facility for
verifying that the eigenvalues computed are the eigenvalues requested. To
know if a given set of 10 eigenvalues comprise the least 10 eigenvalues of a
matrix, it is necessary either to compute all of the eigenvalues or to obtain
information on eigenvalue counts and location through some other means.
This package uses the fact that if A −σI = LDL
T
, then the number of negative
eigenvalues of D is the same as the number of eigenvalues of A that are smaller
than σ. This eigenvalue package uses the sparse symmetric linear equation
package to compute an LDL
T
factorization, where D is a diagonal or
quasi-diagonal matrix.
It is trivial to count the number of eigenvalues of each sign for D. (Technically,
the three numbers giving the number of negative, zero and positive eigenvalues
of D are the inertia of D and A −σI. A related technique for tridiagonal
matrices yielding so-called Sturm sequences can be extended to give the same
information; this name has been carried over in certain engineering contexts to
describe the inertia of the matrix.)
The matrix inertias are used in the following way: The difference between the
number of negative eigenvalues for the associated D matrices for A −σ
2
I and
for A −σ
1
I is the number of eigenvalues in the interval [σ
1
,σ
2
]. If this number
agrees with the number of eigenvalues that the package has computed in this
interval, all of the eigenvalues in this subinterval have been computed. We call
such a subinterval a trust region. The goal of the package is to compute the
number of eigenvalues requested by the user and to find a trust region
including these eigenvalues. To this end, whenever factorizations are
computed, the inertias of the associated matrix are evaluated and saved.
Additional factorizations may be computed to provide trust region information,
so that all returned eigenvalues are confirmed as being properly described.
This use of matrix inertia is subject to rounding errors. A particular difficulty
arises when the shift value σ is actually equal to an eigenvalue. In this case
A −σI should have at least one zero eigenvalue. In practice, the numerical
value is probably very small, but nonzero. However, the matrix inertia
considers only the sign, and so an incorrect count may be returned even when
the factorization is stable.