Next: Direct Methods Up: Introduction Previous: Eigenvalues Sought.   Contents   Index

#### 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 of eigenvalues sought, say to . Few'' is smaller than moderate, say , 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 that are smaller than a given real number or are in a given interval do not require computing the eigenvalues and so can be performed much more cheaply. The key tool is the matrix inertia. The inertia of is the triplet of integers , where is the number of negative eigenvalues of , is the number of zero eigenvalues of , and is the number of positive eigenvalues of . Sylvester's law of inertia states that the inertia of a matrix is invariant under congruence; that is, for all nonsingular matrices , , and have the same inertia. See, for examples, [198, p. 403] or [114, p. 202].

Suppose that the shifted matrix has the LDL factorization

where is a diagonal matrix. Then by Sylvester's law of inertia, . Therefore, the number of negative diagonal elements in from the LDL factorization of gives the number of eigenvalues of smaller than . In the engineering literature, is often called the Sturm sequence number.

It is easy to see that is the number of eigenvalues in the interval , assuming that and the two shifted matrices and are nonsingular. Thus, the cost of counting the number of eigenvalues of in a given interval is equivalent to the cost of two LDL factorizations of and , respectively. This is much cheaper than finding all eigenvalues in . We refer to §10.3 for the software availability of the LDL 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 .

Next: Direct Methods Up: Introduction Previous: Eigenvalues Sought.   Contents   Index
Susan Blackford 2000-11-20