Sign in to follow this  

Calculating eigenvalues

This topic is 4299 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey! Does someone know of some resources which describe how to code a function which calculates the eigenvalues of a matrix? This could be either resources on the net or a book. If you know of a good book which teaches about programming and mathematics together in general I'd be happy to know about it. Thanks in advance!

Share this post


Link to post
Share on other sites
For some info on eigenvalues, peruse this site:

http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/CourseHome/index.htm

EDIT: Actually, I'm not sure if lecture notes, etc, are readily available on that site. I'll look a bit more later. Sorry to disappoint.

Share this post


Link to post
Share on other sites
Thanks alot! I found a quite good lecture on eigenvalues in there (http://ocw.mit.edu/ans7870/18/18.06/tools/all/eigen_lecture_all.html).

But my problem is not really the eigenvalues themselves, the problem is more writing a program which calculates them. I know this is not easy to explain, but if someone could provide some info on the subject, I'd be grateful!

Thanks

Share this post


Link to post
Share on other sites
LAPACK also contains various routines to compute Eigenvalues and Eigenvectors. The code is freely available (unlike the one in numerical recipes) and is used in various scientific applications, so it's probably correct/wellbehaved in all corner cases.

Share this post


Link to post
Share on other sites
I'm not sure how good the numerical recipes are for general non-symmetric matrices, so be careful with them.

If you ever want more detail, I find this book really useful, but I think the best thing you gain from writing your own code to do general eigen decompositions is a deep appreciation for the Lapack functions DGEEV and ZGEEV :)

Share this post


Link to post
Share on other sites
What language are you planning to code in? What kind of matrices will you be dealing with (symmetric or general)? What sizes of matrices will you be working with?

If you are comfortable with FORTRAN, then the LAPACK routines are a readily-available solution.

If you want something C-like, I may be able to help.
I translated one of the EISPACK routines for a Real, General Matrix into C++ and then into javascript. I am just about finished doing the same for a routine that does Real, Symmetric matrices. Once finished, I am planning to post the C++ source code.

(I prefer working from the EISPACK routines because the LAPACK routines include features that might make them more efficient for SOME machines--but doesn't apply to my machine--but makes the code MUCH more difficult to translate.)

Let me know if you are interested, I will then speed up the posting of my code (or perhaps just e-mail you directly).

(I am curious: what do game developers do with eigenvalues?)

Regards,


David

Share this post


Link to post
Share on other sites
For some applications, if you only need the first 2 or 3 eigenvalues/vectors, the fastest and easiest way to compute them is the Power method, which you can google. The idea is if you want the largest eigenvector of A, then if you take any vector v, (A^k)v will start to lean in the direction of the largest eigenvector as k gets large

Share this post


Link to post
Share on other sites
Thanks for all the answers! Im not really a game developer, I am studying physics at university at I need to compute eigenvalues in very large matrices (100x100) for some applications in quantum mechanics. I did do game development some year ago however.

Im planning to do the coding in C/C++. I already made some other functions for matrix/vector algebra (multiplication, determinant...etc) but computing eigenvalues is pretty difficult. The function has to be as general as possible, as I do not really know which kind of matrices I will be working on.

DavidB, Im very interested in your source code. If you want to, it would be nice if you could e-mail it to mailalias@repetit.dk when you have it finished!

Thanks!!

Share this post


Link to post
Share on other sites
Quote:
Original post by DavidB
(I am curious: what do game developers do with eigenvalues?)


From what I understand, both eigenvalues and eigenvectors are very useful and arise quite often wherever things can be expressed by matrices.

E.g. given a 3x3 rotation matrix, its only real eigenvector is the axis, normal to the plane where the rotation takes place.

Or, given the inertia tensor of a solid, its eigenvectors are the principal axes (axes around which angular velocity is collinear to the angular momentum) and the eigenvalues are the moments around those axes. These are useful in dynamics simulations...

I also hear that they are used in solving/modelling resonance problems of vibrating systems. A good motorbike simulation wouldn't be *that good* without them...

Share this post


Link to post
Share on other sites
Quote:
Original post by Repetit

DavidB, Im very interested in your source code.



Hello, Rene

If you know some javascript, you may be able to translate the utilities already posted on my website. For example, here is a javascript routine for calculating the eigenvalues AND eigenvectors of a 6x6, Real, GENERAL matrix. It is a translation of the EISPACK routine RG.F.

http://www.akiti.ca/Eig6Solv.html

The size of the matrix (6) has been hard-coded in this particular routine; however, the algorithm itself is easy to change. You would just have to code a section for the input and output.

For a Real, SYMMETRIC, matrix, I recently finished a modified translation of the EISPACK routine RS.F. The javascript version is here (for a 3x3 matrix):

http://www3.telus.net/thothworks/Eig3RSSolv.html

This translation calculates eigenvalues only, no eigenvectors.

The intro to my C++ source code is here:

http://www3.telus.net/thothworks/EigRSvalosrc.html

Hopefully, your C++ coding skills are better than mine; the algorithm itself is fine, but my dynamic memory management is not the best. You will note that I use an awkward old technique supported by Visual C++ version 6, but which is not proper coding practice. I hope to improve the memory management section in the next two versions, that is why I have created spots for version 1 and 2, to be done later.

Hope this helps.


David

Share this post


Link to post
Share on other sites

This topic is 4299 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this