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]

42 Comments:

Anonymous 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

6:51 PM  
Blogger 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.

5:51 PM  
Anonymous 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?

2:26 AM  
Anonymous 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.

10:20 AM  
Anonymous Anonymous said...

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

5:18 PM  
Blogger 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].

4:38 PM  
Blogger 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.

5:16 PM  
Blogger Xavier said...

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

5:23 PM  
Anonymous Vladimir said...

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.

12:14 AM  
Anonymous 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

5:05 AM  
Anonymous Anonymous said...

Thanks!
just what I was looking for.

Cheers,
DK

12:38 PM  
Anonymous 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

6:20 AM  
Blogger 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.

9:27 AM  
Blogger Adi said...

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

8:14 PM  
Blogger madhur said...

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.

7:31 PM  
Anonymous Anonymous said...

Thank you very much for your code

3:06 PM  
Anonymous 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!

6:24 AM  
Anonymous اليوتيوب said...

i download this i will need it

8:45 AM  
Blogger 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.

11:52 PM  
Blogger 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

5:17 AM  
Blogger 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!

8:27 AM  
Blogger 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!

2:12 AM  
Blogger Photonyx said...

Hi Connelly,

Thanks for the code, works like a charm!

4:07 PM  
Blogger 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

2:31 PM  
Blogger 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

3:43 AM  
Blogger muhammad kumail said...

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

3:55 AM  
Blogger saleem mohd. said...

Free Social Media Marketing where Every thing will be Free, Facebook Likes, Twitter Followers, Twitter Tweets, Twitter Re-Tweets, Twitter Favorites, Google Plus Followers, StumbleUpon Followers, Youtube Views, Youtube Likes, Youtube Subsribes, Pinterest Followers, Pinterest Likes, Pinterest PinIt, Free Website Visitors.
Just Join now and Free Increase your Social Media Networks.
GetLikeFast.com

12:47 AM  
Blogger 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

12:24 AM  
Blogger 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

2:42 PM  
Blogger faisal altaf said...

Free Facebook Likes, Twitter Followers, Twitter Tweets, Twitter Re-Tweets, Twitter Favorites, Google Plus Followers, StumbleUpon Followers, Youtube Views, Youtube Likes, Youtube Subsribes, Pinterest Followers, Pinterest Likes, Pinterest PinIt, Free Website Visitors.
Just Join now and Free Increase your Social Media Networks.
GetLikeFast.com

5:44 AM  
Blogger 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

2:26 AM  
Blogger Brad maddox said...

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

1:46 PM  
Blogger mirza usman said...

Latest Currency news updates, latest forex trading business updates, trading updates, forex trading latest news, forex brokers directory, forex brokers list, Dollars news affairs, Stock Markets, stock market news, stock market analysis, technology news, international forex markets, international forex business news and all updates about Forex Trading
ForexAffairs.Com

1:27 AM  
Blogger hammad sohail said...

Forex Affaris.. Latest Currency news updates, latest forex trading business updates, trading updates, forex trading latest news, forex brokers directory, forex brokers list, Dollars news affairs, Stock Markets, stock market news, stock market analysis, technology news, international forex markets, international forex business news and all updates about Forex Trading
ForexAffairs.Com

3:10 AM  
Blogger 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

8:42 PM  
Blogger 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.

5:56 PM  
Blogger 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

1:07 AM  
Blogger hammad sohail said...

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

1:52 AM  
Blogger Adeola Adisa said...

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

10:30 PM  
Blogger samad abbas said...

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

9:50 AM  
Blogger abdallah eldeeb said...

تعليم الكترونى

3:33 AM  
Blogger muhammad yasir bawani said...


Find home based jobs of link building, facebook marketing, add marketing, add clicking and much more jobs.
www.jobzcorner.com

1:17 PM  

Post a Comment

<< Home