## Friday, February 09, 2007

### Eigenvectors of 3x3 symmetric matrix

A C++ source and header file to compute eigenvectors/values of a 3x3 symmetric matrix. Potentially easier than installing EISPACK, LAPACK, or Gandalf if you only need this single function. Takes about 6000 clock cycles per call on my Pentium 4. Public domain. [1]

pete said...

Hi Connelly,

Thanks for the eigensystem code. I need to find the magnitude and direction of the principle axes of a covariance matrix and plot the resulting ellipsoid. This should save me a bunch of time.

Cheers,
Pete

Connelly said...

No problem. I used this code to plot level sets of quadric error functions when implementing Garland and Heckbert's mesh simplification paper [1], so like you, I was plotting ellipsoids.

Anonymous said...

Hi Connelly,
I found an error in the code. When I was testing the next matrix:

0 -0.00018 0.01718
0.00016 5e-05 0.01373
-0.01474 -0.0225 0.43942

The results are:

evalues:
-0.00146067 -0.000130409 0.441061
evectors:
0.520977 0.852918 -0.0333759
0.851398 -0.522042 -0.0509365
0.0608683 0.00187936 0.998144

This results are different in MATLAB. Is it normal?

Anonymous said...

This should work only for 3x3 *symmetric* matrix. The next matrix doesn't seem to be symmetric to me.
Thanks for the code.

Anonymous said...

I need to find only an eigenvector corresponding to the smallest eigenvalue. Is there something faster for that?

Connelly said...

For more speed, if you need the eigenvector for the eigenvalue of smallest or largest absolute value, you can try power iteration [1] or inverse power iteration [2]. You might be able to get two eigenvectors by using both power iteration and inverse iteration. The third can be obtained by a cross product. Once you have one eigenvector you can also try reducing the dimension of the problem by one (by projecting on to vectors orthogonal to the found eigenvector) and then solving again by any method of your choice. Once you get to two dimensions there is a nice closed form formula for the eigenvectors based on the quadratic formula.

It would be interesting to see how few clock cycles are needed for solving the 3x3 and 4x4 problems for the symmetric and non-symmetric cases. Maybe there's already code out there which solves these problems quickly; does any one know where it is?

For generality, you can change the constant N given in the code to solve for whichever dimension you need. Changing N to a variable might slow down the optimizer; I didn't check. If solving for a non-symmetric matrix, you can steal the code needed from the public domain package JAMA [3].

Connelly said...

One might also try solving the characteristic polynomial for eigenvalues and then using linear algebra to solve for the associated eigenvectors. Using one of the aforementioned techniques for the 3x3 case, one could probably speed up the code by an order of magnitude.

Xavier said...

Hi, thanks for the code. It worked fine for me.

Thanks you for your code. I will use it (until write my own) to calculate OBBs (object oriented boxes), that are used in computer graphics for interference detection.

Sam said...

I am having a lot of trouble finding the eigen vectors of a non symmetric matrix..Is their any way you would know how to go about it

Anonymous said...

Thanks!
just what I was looking for.

Cheers,
DK

Anonymous said...

Seems to have slightly different output than with MATLAB.
For example for input=

1.0000 0.9794 0.6967
0.9794 1.0000 0.7742
0.6967 0.7742 1.0000

in MATLAB I get:
Eigenvectors =

-0.5890 -0.6535 -0.4754
-0.6049 0.7466 -0.2769
-0.5359 -0.1245 0.8351

Eigenvalues =

2.6397
0.0137
0.3466

While with your code I get:
Eigenvectors =
-0.65348666890016993 -0.47540875028028978 0.58901756656885285
0.74663228601038611 -0.27687590315051447 0.60488012344719444
-0.12448053284214880 0.83506062918300739 0.53589023365966881

Eigenvalues=
0.013661896296036690
0.34664732510150514
2.6396907786024602

As you can see, the signs on the right column eigenvector are different to the first column at MATLAB (which are the same eigenvector)...
I suppose there is a bug?

DK

Connelly Barnes said...

DK - No bug. If A * v = lambda * v, then A * (-v) = lambda * (-v) also, so if v is an eigenvector then -v is also, and eigenvectors aren't uniquely defined up to sign.

Oes Tsetnoc one of the ways in which we can learn seo besides Mengembalikan Jati Diri Bangsa. By participating in the Oes Tsetnoc or Mengembalikan Jati Diri Bangsa we can improve our seo skills. To find more information about Oest Tsetnoc please visit my Oes Tsetnoc pages. And to find more information about Mengembalikan Jati Diri Bangsa please visit my Mengembalikan Jati Diri Bangsa pages. Thank you So much.
Oes Tsetnoc | Semangat Mengembalikan Jati Diri Bangsa

Hi Connelly,

Thanks for the code. It works fine for 3X3 symmetric matrix. Although, I was just curious to know which algorithm they have applied to calculate the eigenvalues and especially for eigenvectors.

I was trying to implement Row Reduced Echelon form method to calculate the eigenvector, but unfortunately it didn't work as I would have expected.

Thanks again.

Anonymous said...

Thank you very much for your code

Sildenafil Citrate said...

I tried this code for 3X3 symmetric matrix, and I had a couple of problems and I hope that somebody could help me work this out, thanks in advance!

اليوتيوب said...

zhengbin said...

Kauf und Verkauf von Gold in den thomas sabo Goldmarkt hat viel an Popularität gewonnen, sind thomas sabo shop Gold-Nuggets und Goldmünzen im Handel erhältlich herkömmlichen thomas sabo jewellery Wege der Kauf und Verkauf bei niedrigen wenn thomas sabo schmuck high.Tips Gold und Silver.Have eine thomassabo online shop klare Vorstellung davon, warum die Schmuck thomas sabo onlineshop verkaufen muss, um verkauft werden und Scout für die sabo schmuck entsprechende buyer.Volume aus Gold oder thomas sabo shop online Silber zu einem Zeitpunkt verkauft werden bestimmen den Verkaufspreis und die Verhandlungsmacht thomas sabo charm club der seller.Purity bestimmt auch den Endpreis der verkauften Artikel.

gorgie-smith said...

I've been reading the blog and I love the way like you redact the information, specially when you attached Generic Viagra on the blogroll. 23jj

asdfg said...

Hey Connelly,
even if this thread is not perfectly recent, perhaps someone using the code could help me: At line 193 d[m] is accessed, after m may be incremented up to 3 by lines 159ff. as d should be of length 3, this is a problem. Also later, in the loop @ 200ff m being 3 leads to out-of-bounds indices.
Do you have any advice. I don't really know the algorithm, so it's hard to solve that.
Thanks!

asdfg said...

Sorry, had a typo in the syntax conversion (needed it in python). m=3 cannot occur in this algorithm.
Another remark: in the resulting matrix, V[i] is not the ith Eigenvector, but [V[0][i],V[1][i],V[2][i]] is.
Thanks!

Photonyx said...

Hi Connelly,

Thanks for the code, works like a charm!

David Doria said...

Connelly,

Thanks, this is really useful. It might be nice to include a demo like this to indicate the ordering properties of the arrays:

#include

#include "eig3.h"

int main(int argc, char*argv[])
{

// Create the matrix
// (1 4 0)
// (4 2 0)
// (0 0 5)
double A[3][3];
A[0][0] = 1;
A[0][1] = 4;
A[0][2] = 0;
A[1][0] = 4;
A[1][1] = 2;
A[1][2] = 0;
A[2][0] = 0;
A[2][1] = 0;
A[2][2] = 5;

// Allocate memory for the eigenvalues/vectors
double V[3][3];
double d[3];

// Perform the decomposition
eigen_decomposition(A, V, d);

// Output the result
std::cout << "Eigenvalues: " << d[0] << " " << d[1] << " " << d[2] << std::endl;

std::cout << "Eigenvector 0: " << V[0][0] << " " << V[1][0] << " " << V[2][0] << std::endl;
std::cout << "Eigenvector 1: " << V[0][1] << " " << V[1][1] << " " << V[2][1] << std::endl;
std::cout << "Eigenvector 2: " << V[0][2] << " " << V[1][2] << " " << V[2][2] << std::endl;

return 0;
}

David

zain ul abidin kk said...

Any thing you want in Entertainment for Fun... Entertainment Articles, Entertainment News, Entertainment Pictures, Bollywood, Hollywood and Lollywood Pictures and Videos, Entertainment Latest updates, Hot Entertainment News and Pictures Funny Entertainment Pictures, lol Pictures, Funny Pictures and Much More Fun Only on 1 Current Affairs Network
hotcurrentaffairs.com

Earn Money Launch a New Earning System on Facebook, the best Social Media Website where you can share some fun and earn with us, Share some pictures on Facebook and earn on every pictures you post or share. Unlimited Facebook Wall Sharing and Unlimited Earning.
Earn with Making Facebook Ids, Make Unlimited Facebook Ids and Get 10\$ on Every FB Id.
jobzcorner.com

saleem mohd. said...

GetLikeFast.com

Habeib Khan said...

Lols Gag is the the Best Lol Network Ever, where you can every thing is lol and Funny, Troll Images, Funny Vidoes, Prank Peoples, Funny Peoples, Prank Images, Fail Pictures, Epic Pictures, Epic Videos, Prank Videos, Fail Videos and Much More Fun and Entertainment, Lols and Gags, Lol Pictures, Lol Videos, Funny Pictures, Lol is the Laugh out of Laugh where you can Fun Unlimited and Laughing Unlimited.
lolsgag.com

kamran shiakh said...

Lols Gag is the the Best Lol Network Ever, where you can every thing is lol and Funny, Troll Images, Funny Vidoes, Prank Peoples, Funny Peoples, Prank Images, Fail Pictures, Epic Pictures, Epic Videos, Prank Videos, Fail Videos and Much More Fun and Entertainment, Lols and Gags, Lol Pictures, Lol Videos, Funny Pictures, Lol is the Laugh out of Laugh where you can Fun Unlimited and Laughing Unlimited.
lolsgag.com

faisal altaf said...

GetLikeFast.com

Habeib Khan said...

Top 7 Expensive Cars, Top Most Popular Cars, Cars and Vehicles with Info and Pictures, Upcoming Latest cars and vehicles, Latest Mazda Models, Racing Cars, International Sport Cars, Concept Cars, PS-Pod, Strange Vehicles, Nissan, Royce Corniche, Ford Concept Cars, Strange Vehicles, Mercedes and More Sport Cars and Vehicles with Pictures and Info
WorldLatestVehicles.com

Upcoming Latest cars and vehicles, Latest Mazda Models, Racing Cars, International Sport Cars, Concept Cars, PS-Pod, Strange Vehicles, Nissan, Royce Corniche, Ford Concept Cars, Strange Vehicles, Mercedes and More Sport Cars and Vehicles with Pictures and Info
WorldLatestVehicles.com

mirza usman said...

ForexAffairs.Com

ForexAffairs.Com

faisal said...

lol and Funny, Troll Images, Prank Peoples, Funny Peoples, funny planet, funny facts, funny cartoons, funny movies pics, iphone funny, funny jokes, Prank Images, Fail Pictures, Epic Pictures, Lols and Gags, Lol Pictures, Funny Pictures, Lol is the Laugh out of Laugh where you can Fun Unlimited and Laughing Unlimited.
LolsGag.Com

Miguel Braganza said...

------------------------------
undefined reference to 'WinMain@16'
ld returned 1 exit status.
------------------------------
I'm using Dev C++ 4.9.9.2
and I was to encounter this message and the program does not run.
Should I change something in the code or what? Thank You Connelly.

zubair saleem said...

Classified Sites, Pakistani Classified Sites, USA Classifieds, Indian Classifieds, Entertainment Articles, Entertainment News, Entertainment Pictures, Bollywood, Hollywood and Lollywood Pictures and Videos, Entertainment Latest updates, Hot Entertainment News and Pictures Funny Entertainment Pictures, lol Pictures, Funny Pictures and Much More Fun Only on 1 Current Affairs Network
hotcurrentaffairs.com

Super Cars Latest Mazda Models, Racing Cars, International Sport Cars, Concept Cars, PS-Pod, Strange Vehicles, Nissan, Royce Corniche, Ford Concept Cars, Strange Vehicles, Mercedes and More Sport Cars and Vehicles with Pictures and Info
SuperCars.Com

hi.i want to use c++ to decompose received signal in order to obtain the eigen values and vector. please can you explain. thanks

Top Ten Classified Website List, Pakistani Classified Sites, USA Classifieds, Indian Classifieds, Entertainment Articles, Entertainment News, Entertainment Pictures, Bollywood, Hollywood and Lollywood Pictures and Videos, Entertainment Latest updates, Hot Entertainment News and Pictures Funny Entertainment Pictures, lol Pictures, Funny Pictures and every thing you want...
www.hotcurrentaffairs.com

abdallah eldeeb said...