Eigenshuffle

Consistently sorted eigenvalue and eigenvector sequences
6,8K download
Aggiornato 5 giu 2020

Visualizza la licenza

A problem that I've seen many times on the newsgroup is how eig returns its eigenvalues and eigenvectors. By itself, eig returns an arbitrary order for the eigenvalues and eigenvectors. They are often nearly sorted in order, but this is not assured. The other issue is the eigenvectors can have an arbitrary sign applied to them.

Worse, when you have a sequence of eigenvalue problems, the eigenvalues can sometimes cross over. One would like to sort the eigenvalues/eigenvectors so the sequence is consistent.

I've designed eigenshuffle.m to do exactly that. It takes a pxpxn array, where each page of the array is one matrix where we wish to compute the eigenvalues. Eigenshuffle tries to permute the eigenvalues and eigenvectors to be maximally consistent from one step in the sequence to the next. Eigenshuffle also chooses the sign to be applied to each eigenvector to be maximally consistent with the the vectors prior to it in the sequence of eigenproblems.

As an example, try this simple matrix function of a parameter t.

Efun = @(t) [1 2*t+1 t^2 t^3;2*t+1 2-t t^2 1-t^3; ...
t^2 t^2 3-2*t t^2;t^3 1-t^3 t^2 4-3*t];

Aseq = zeros(4,4,21);
for i = 1:21
Aseq(:,:,i) = Efun((i-11)/10);
end
[Vseq,Dseq] = eigenshuffle(Aseq);

To see that eigenshuffle has done its work correctly,
look at the eigenvalues in sequence after the shuffle.

t = (-1:.1:1)';
[t,Dseq']
ans =
-1 8.4535 5 2.3447 0.20181
-0.9 7.8121 4.7687 2.3728 0.44644
-0.8 7.2481 4.56 2.3413 0.65054
-0.7 6.7524 4.3648 2.2709 0.8118
-0.6 6.3156 4.1751 2.1857 0.92364
-0.5 5.9283 3.9855 2.1118 0.97445
-0.4 5.5816 3.7931 2.0727 0.95254
-0.3 5.2676 3.5976 2.0768 0.858
-0.2 4.9791 3.3995 2.1156 0.70581
-0.1 4.7109 3.2 2.1742 0.51494
0 4.4605 3 2.2391 0.30037
0.1 4.2302 2.8 2.2971 0.072689
0.2 4.0303 2.5997 2.3303 -0.16034
0.3 3.8817 2.4047 2.3064 -0.39272
0.4 3.8108 2.1464 2.2628 -0.62001
0.5 3.8302 1.8986 2.1111 -0.83992
0.6 3.9301 1.5937 1.9298 -1.0537
0.7 4.0927 1.2308 1.745 -1.2685
0.8 4.3042 0.82515 1.5729 -1.5023
0.9 4.5572 0.40389 1.4272 -1.7883
1 4.8482 -8.0012e-16 1.3273 -2.1755

Here, columns 2:5 are the shuffled eigenvalues. See that the second eigenvalue goes to zero, but the third eigenvalue remains positive. We can plot eigenvalues and see that they have crossed, near t = 0.35 in Efun.

plot(-1:.1:1,Dseq')

For a better appreciation of what eigenshuffle did, compare the result of eig directly on Efun(.3) and Efun(.4). Thus:

[V3,D3] = eig(Efun(.3))
V3 =
-0.74139 0.53464 -0.23551 0.3302
0.64781 0.4706 -0.16256 0.57659
0.0086542 -0.44236 -0.89119 0.10006
-0.17496 -0.54498 0.35197 0.74061

D3 =
-0.39272 0 0 0
0 2.3064 0 0
0 0 2.4047 0
0 0 0 3.8817

[V4,D4] = eig(Efun(.4))
V4 =
-0.73026 0.19752 0.49743 0.42459
0.66202 0.21373 0.35297 0.62567
0.013412 -0.95225 0.25513 0.16717
-0.16815 -0.092308 -0.75026 0.63271

D4 =
-0.62001 0 0 0
0 2.1464 0 0
0 0 2.2628 0
0 0 0 3.8108

With no sort or shuffle applied, look at V3(:,3). See that it is really closest to V4(:,2), but with a sign flip. Since the signs on the eigenvectors are arbitrary, the sign is changed, and the most consistent sequence will be chosen. By way of comparison, see how the eigenvectors in Vseq have been shuffled, the signs swapped appropriately.

Vseq(:,:,14)
ans =
0.3302 0.23551 -0.53464 0.74139
0.57659 0.16256 -0.4706 -0.64781
0.10006 0.89119 0.44236 -0.0086542
0.74061 -0.35197 0.54498 0.17496

Vseq(:,:,15)
ans =
0.42459 -0.19752 -0.49743 0.73026
0.62567 -0.21373 -0.35297 -0.66202
0.16717 0.95225 -0.25513 -0.013412
0.63271 0.092308 0.75026 0.16815

Note that sequences of generalized eigenvalue problems can now be solved too.

With many thanks to Yi Cao, I've included munkres by permission as a subfunction here.

http://www.mathworks.com/matlabcentral/fileexchange/20652

Cita come

John D'Errico (2024). Eigenshuffle (https://www.mathworks.com/matlabcentral/fileexchange/22885-eigenshuffle), MATLAB Central File Exchange. Recuperato .

Compatibilità della release di MATLAB
Creato con R2007b
Compatibile con qualsiasi release
Compatibilità della piattaforma
Windows macOS Linux
Categorie
Scopri di più su Linear Algebra in Help Center e MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Versione Pubblicato Note della release
2.0.0.0

Allows for the computation of generalized eigenvalues, by allowing the user to provide a Bsequence array of the same size and shape as Asequence.

1.4.0.0

Jonas is correct, that munkres gives a significant gain in the speed of my own code. I was planning on putting in a test to see if munkres exists on your machine, then to use munkres, but Yi Cao was gracious to allow me to include his code.