Page 1 of 1

Order of eigenvalues

PostPosted: Tue Dec 11, 2012 10:36 am
by mike.wimmer
Dear all,

unless explicitly asked for, the eigenvalue routines for general matrices (for example xGEES, xGEEV) do not sort the eigenvalues. However, I have noticed in many applications (with matrices of various structure) that typically the larger eigenvalues come first, i.e. that the eigenvalues are typically almost sorted in descending order.

Now, if the eigenvalues were calculated using a power method, the fact that the largest eigenvalue comes first is somewhat obvious. As far as I understand, xGEES/xGEEV is based on the Francis QR algorithm, and while still related to the power method, the shifts used there make the order far less obvious. In fact, Golub and van Loan state in "Matrix computations" (Chap 7.5.6): The order of the eigenvalues along the diagonal of T is somewhat arbitrary (T is the triangular matrix of the Schur decomposition).

Can one still in general expect the behavior of LAPACK I was describing, i.e. that the eigenvalues are almost ordered? Do you have some insight why this is?

Some background: I'm asking this question also because of some practical matter. We have a problem where we need the invariant subspace for some eigenvalues, which we can get by reordering the Schur decomposition. This reordering is faster, if the eigenvalues are already close to the top of the triangular matrix T. It turns out that we can formulate our problem such that the desired eigenvalues are either the smallest or the largest. From my observation mentioned above, it would seem that making them largest is best for our application, but I'm wondering how general this is.

Re: Order of eigenvalues

PostPosted: Tue Dec 11, 2012 4:25 pm
by mike.wimmer
I was a bit inaccurate in my description above: With largest eigenvalue, I mean largest in absolute value.