version 2.0.0.0 (28.9 KB) by
John D'Errico

Consistently sorted eigenvalue and eigenvector sequences

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.

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

Created with
R2007b

Compatible with any release

- MATLAB > Mathematics > Linear Algebra >

**Inspired by:**
Hungarian Algorithm for Linear Assignment Problems (V2.3)

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

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

Zhaoshun DengIt works very well most of time. However, in one case (root locus), the orders of one complex root and a real root are exchanged when their real parts approach each other. Hope you can fix it.

Mark R.I am trying to solve a generalized eigenvalue problem with 1000 iterations.(1000 generalized problems with a slight change of a variable each time to obtain dispersion curves). I first used the "sort" function ,which gives almost correct curves but does not allow the crossing of modes. At this point the running time of the code is 15secs. When i try to solve this problem using eigenshuffle the code runs for more than 8 hours. Am I doing something wrong or does the function actually need so much time ?? And is there a way to reduce this time ??

harleykittenYisheng ZhengMax NusspickelIs the implementation for generalized eigenvalue problems correct? It seems the B metric is only used in the eigensolver, but I would expect it also needs to be dotted between v1' and v2 in the distance matrix?

John D'ErricoI've updated the code to now allow a Bsequence array to be provided. If so, and if Bsequence is of the same size and shape as Asequence, then generalized eigenproblems will be solved. The code still works as before if Bsequence is not provided at all.

Aramis Schwanka TrevisanJinpeng GuoThiago BurghiThank you!

Massimiliano InsinnaYi EgolQuite useful,thx a lot!

Bo Weithanks a lot!

shaojiang wuJohnInteresting approach, but appears to assume that the eigenvector element order isn't modified, essentially solving dxdt = A x, where the x sequence order is defined. A potential modification would be y = B x, dxdt = A x, then assume the sequence of y measurements are fixed, and not the unmeasured x states. Easy modification is to change V1, V2 to B * Vseq.

siyue lianghow to download this .m file.I can see the downloadzip ,but i can not downdload when i choose it. if anyone can help me ,could u please send the file which u have download to me ? my email is 1020784568@qq.com

ChrisExcellent code for solving arrays of eigenvalue problems with real solutions. Would like to see a better distance/cost function for systems with complex solutions. Would love to hear suggestions if others have them.

Jacob Langlife saver. thanks for this.

Michael Chanworks great! thanks a lot.

Antonio HortalQingyuworks great!

Jacopo MarconiGenius! thanks a lot, I was going crazy

Mathieu LachapelleOne thousand thanks (that's the number of time my program uses your function)

Juan PabloWilliamWorks very well. Not only performs the eig function over arrays of matrices, but sorts the eigenvalues and eigenvectors in a rational way.

MeganIt was great, Thanks.

LauraThis is exactly what I needed. Unfortunately, it doesn't seem to work on eigenvalue problems where the crossings happen over a wide range, or where they cross and then cross back. For my system, this really only worked for small crossings.

Sandor TothGreat code!

pushkarinipushkarinicomfort.

ALouie LuLouie LuA minor suggestion: could put the output argument Dseq in front of Vseq, so that Dseq=eigenshuffle(A) can be used when Vseq is not wanted.

Maurizio De Pitta'OndrejI thought so, that it couldn't be any harder than eigenvalues, but then I looked here

http://www.math.uu.nl/publications/preprints/1180.ps

Actually the code there seems to work pretty well. So schurly, no need to reinvent schurshuffle

John D'ErricoFor schur, I'd like to help. But schurly, then I would have to call the solution the schurshuffle.

http://www.youtube.com/watch?v=0V-VgRqsEcg

Seriously, it seems the same methodology would work. And with a name like the schurshuffle, I'd hate to pass up the opportunity.

OndrejIs it possible to write the same functionality but for schur decomposition? Schur function in matlab returns the eigenvalues on diagonal in same order as eig function..which is not always nice. Thanks.

Yi CaoJohn,

This is novel. A possible application is for MIMO frequency response. The following example needs control system toolbox:

sys = rss(10,10,10);

w=logspace(-1,1,200);

H=freqresp(sys,w);

[V,D]=eigenshuffle(H);

semilogx(w,D)

Another thing you may consider is to alter the distance measure to the true distance between scaled eighenvectors of two permutations, i.e. define

y_i(k) = lambda_i(k) v_i(k) = lambda_i(k) A(k), for i = 1, ..., n

to pair the ith of A(k) with the jth of A(k-1), the distance

d_ij = |y_i(k)|^2 + |y_j(k-1)|^2 - 2 |y_i(k)| |y_j(k-1)| cos < y_i(k), y_j(k-1)

where

cos < y_i(k), y_j(k-1) = v_i(k)^T v_j(k-1)

Regards,

Yi

ChrisFantastic program which does exactly what I needed - thanks!

DNFIf you check out the other ratings of this 'Xu Wings' you will see he has a thing in for D'Errico and possibly also Oliver Woodford. It seems possible that 'Xu Wings' is an alias for Shahab Anbarjafari.

Kenneth EatonXu, I can only guess that you have very little experience with MATLAB and even less knowledge of whom you are criticizing.

Xu Wingsi found the level of the code very low, possibly a good high school boy in here can write such a programme!

Jonas LundgrenAnd the updated rating.

John D'ErricoJonas is absolutely correct, and I had even thought to offer munkres (once I learned of its existence) as the underlying permutation engine in this code, with a test to see if the user had downloaded munkres. Yi Cao was gracious to allow me to include munkres as a subfunction however, so I have included his current version.

The munkres powered version of eigenshuffle is now about 4 times faster for small (4x4) systems. For larger systems on the order of 15x15, I'd expect nearly a 20-1 speedup. Larger systems that that will be even faster compared to the previous release of this code.

Even better, the use of munkres as the permutation engine may sometimes provide a better choice of permutation than did my own minimum trace scheme, so the user wins in two ways here.

Many thanks to Yi Cao for munkres, and to Jonas Lundgren for his comments on the code.

Jonas LundgrenI missed the comment. Eigenshuffle works very well on all the test problems I have tried. The distance measure is clever! If you replace MINTRACE by MUNKRES of Yi Cao, it will be fast as well.

Jonas LundgrenJohn D'ErricoI've uploaded a new version that works better for complex problems.