473,725 Members | 2,020 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

How to find the eigenvalues of a matrix

79 New Member
I need a practical method to find the eigenvalues of a matrix in C++ because the one I know(the only one I know) is to subtract the elements of the diagonal by the eigenvalue and then find the determinant of this matrix: |A-xI|=0, and in C++ I do this by checking every float value with one digit after the decimal between -10000.0 and 10000.0, and I can already find the determinant.
This is its code:
Expand|Select|Wrap|Line Numbers
  1. float ev=-10000;
  2. while(ev<=10000)
  3. {
  4. /*subtract the diagonal elements of the matrix by ev*/
  5. if(determinant(matrix)==0)
  6.     {
  7.         /*store the value ev in a one dimensional array*/
  8.         ev=ev+0.1;
  9.     }
  10. }
  11.  
and of course if this worked I wouldn't have posted the question. I AM NOT asking for the code, I just want a practical way to find the eigenvalues in C++.
Thank you for reading the question.
PS: If you could tell how to find the order of an eigenvalue too that would be great.
Sep 9 '08 #1
9 28962
TamusJRoyce
110 New Member
If you are looking for a better method, I can suggest a book that has it in it... Numerical Recipies in C++ .

The link may not be the book I'm thinking of, but I'm sure it still has excellent information about how to do matrix math.

Also, research how gnu gsl produces it's eigenvalues. gsl is among the fastest open-source libraries, and I'm sure googling for specifics on how gsl works is available.
Sep 10 '08 #2
arnaudk
424 Contributor
To say that answering your question would require a chapter of a book would be an understatement. I think you'd be a bit loopy to try to write your own code for this unless you intend to make a career out of writing numerical routines. Indeed, the "Numerical Recipes in C++" book does contain some routines but after introducing a lot of theory it states
You have probably gathered by now that the solution of eigensystems is a fairly complicated business. It is. It is one of the few subjects covered in this book for which we do not recommend that you avoid canned routines. On the contrary, the purpose of this chapter is precisely to give you some appreciation of what is going on inside such canned routines, so that you can make intelligent choices about using them, and intelligent diagnoses when something goes wrong.
The routines you require are covered in a series of academic articles published in a collection edited by J. H. Wilkinson and C. Reinsch called "Handbook for Automatic Computation, vol. 2, Linear algebra." They have since been implemented in FORTRAN, in the EISPACK set of routines, which has been ported to C in CLAPACK and GSL and commercial C++ packages like NAG. If you actually want to implement them yourself, then invest in a copy of that handbook or Numerical Recipes in C++ because you'll really need it.

An improvement on what you're currently doing would be to derive the characteristic equation symbolically and solve for the roots of the resulting polynomial (numerically or symbolically), which will also tell you the multiplicity of degenerate eigenvalues but that will require a fundamental rewrite you your code and I'm not sure it will be feasible for any sizable matrices. If you want to embark on that magical journey, then research symbolic computation.
Sep 10 '08 #3
curiously enough
79 New Member
If you are looking for a better method, I can suggest a book that has it in it... Numerical Recipies in C++ .

The link may not be the book I'm thinking of, but I'm sure it still has excellent information about how to do matrix math.

Also, research how gnu gsl produces it's eigenvalues. gsl is among the fastest open-source libraries, and I'm sure googling for specifics on how gsl works is available.
Thanks, the book says that there is a lot of other ways to find the eigenvalues(and of course not mentioning what those ways are and making me look for them, which I still am), and hopefully they can be applicable to C++.
Sep 10 '08 #4
curiously enough
79 New Member
To say that answering your question would require a chapter of a book would be an understatement. I think you'd be a bit loopy to try to write your own code for this unless you intend to make a career out of writing numerical routines. Indeed, the "Numerical Recipes in C++" book does contain some routines but after introducing a lot of theory it states

The routines you require are covered in a series of academic articles published in a collection edited by J. H. Wilkinson and C. Reinsch called "Handbook for Automatic Computation, vol. 2, Linear algebra." They have since been implemented in FORTRAN, in the EISPACK set of routines, which has been ported to C in CLAPACK and GSL and commercial C++ packages like NAG. If you actually want to implement them yourself, then invest in a copy of that handbook or Numerical Recipes in C++ because you'll really need it.

An improvement on what you're currently doing would be to derive the characteristic equation symbolically and solve for the roots of the resulting polynomial (numerically or symbolically), which will also tell you the multiplicity of degenerate eigenvalues but that will require a fundamental rewrite you your code and I'm not sure it will be feasible for any sizable matrices. If you want to embark on that magical journey, then research symbolic computation.
So in short you are saying is that there is no other method unless I want to be a math proffessor. I don't mind if the method is long or difficult, if you could show me a direct link to it that would solve the problem.

And I don't really understand how I should derive the chrachteristic polynomial in the algorithm, neither do I know what numerically or symbolically mean. If you could clearify a bit(since you seem to know a lot about it).
Sep 10 '08 #5
arnaudk
424 Contributor
I've always used canned routines so I don't know what it really involves but it seems like a complex and time consuming task. Since it looks like you're really getting into heavy numerics so you should invest in a good book on the subject like Numerical Recipes where you'll find detailed answers to many such problems. Why reinvent the wheel?

The characteristic equation is det(A - x*I) = 0 where A is an nxn matrix and I is the nxn identity matrix (a matrix with ones on the diagonal and zeros elsewhere). Expanding the determinant results in a polynomial equation in x

a_n*x^n + ... + a_1*x + a_0 = 0

There is often a slow sloppy way to do things and in this spirit I suggested that you could try to determine your characteristic equation symbolically, namely, to determine the coefficients a_0, a_1, ... a_n. This means that you will need to evaluate your determinant not by plugging in values for x but by working with the symbol x, keeping track of its powers and coefficients as the determinant is evaluated. In the end you will have reduced the eigenvalue problem to the simpler problem of finding the roots of an n-degree polynomial. For the latter you can use a basic bracketing scheme or something more sophisticated like Laguerre's method. Or you could again symbolically do polynomial long-division to factorize it into (x - x_0)(x - x_1)...(x - x_n) where your eigenvalues would then be x_0,...,x_n and you'll know how many repeated eigenvalues (multiplicity of the eigenvalues) you have.

By far the slowest and sloppiest way would be to find roots of det(A - x*I)=0 directly, using standard methods like bracketing, or Brent's method and evaluating your determinant for each iteration of the root finder. Coupled with your slow minors-expansion method of finding the determinant, I believe this will be unfeasible for matrices of any reasonable size, and you will most likely miss eigenvalues outside your search region and imaginary eigenvalues and eigenvalues which are too close to each other, but it will better than your random search method proposed above.

I should reiterate that the standard methods presented in books like NR are vastly superior, they are faster and treat difficulties like two roots being close to each other, imaginary roots, etc.
Sep 11 '08 #6
arnaudk
424 Contributor
Thanks, the book says that there is a lot of other ways to find the eigenvalues(and of course not mentioning what those ways are and making me look for them, which I still am), and hopefully they can be applicable to C++.
If you want names, in NR the Given's method or Householder methods are used to bring real, symmetric matrices to tridiagonal form. Then the QR or "QL with implicit shifts" algorithms are used to find the eigenvalues or, also mentioned but not discussed are the "divide-and-conquer" and MRRR (Multiple Relative Robust Representation) methods. Non-symmetric matrices are reduced to Hessenberg form using the Householder method or Gaussian elimination with pivoting and then the QR algorithm is applied. Then there are methods for complex matrices....
Sep 11 '08 #7
JosAH
11,448 Recognized Expert MVP
Also check the power method: x_i+1 == A*x_i, normalize the x_i's until both the
x_i+1 and x_i are a (near) multiple of each other. That multiple is the largest
eigen value and the last x_i+1 value is an eigen vector. Given this eigen vector
and value you can fiddle diddle a bit with matrix A in order to find the next largest
eigen value and vector. Google is your friend.

kind regards,

Jos
Sep 11 '08 #8
TamusJRoyce
110 New Member
Tip: Never forget about precision when coding equations. Especially with eigenvalues (where the more rows/columns you have, the more messy the precision can get). Numerical Recipies in C++ contains that as well, but any Numerical Calculus book/online resource should have calculating precision included.

I'm sure other methods than simply using the determinant will help on this regard, but don't let precision slip by...I guess it's one reason I try to stick to using libraries like gsl such as arnaudk does : )

Another type of book that is good is Linear and Nonlinear Programming. It uses matrices & eigenvalues on optimization problems. Maybe something you would want to learn to take your C++ eigenvalue code to the next level?
Sep 12 '08 #9
happyrockz
1 New Member
// EigRSvalo - Program for calculating the Eigenvalues ONLY of a N X N real, symmetric matrix.
Oct 30 '08 #10

Sign in to post your reply or Sign up for a free account.

Similar topics

13
5861
by: Havatcha | last post by:
Does anyone know of a decent (free/easy to use) C++ library for manipulating matrices and caculating eigenvalues, eigenvectors and so on? I intend to add some Principal Component Analysis functionality to some software. Any recommendations appreciated.
3
4648
by: rickz | last post by:
Hi, Does anybody know where I can find the matrix computation components in .NET framework? Do I need to use a third-party one or there's one that comes with the framework libraries? Thanks!
2
2168
by: Carlos Villaseñor M. | last post by:
Hi every body I'm still new to C#, and at this time I'm developing my firt application (console application to learn the lenguage), and I need to perform matrix operations like multiply, to invert, to transpose and find eigenvalues an eigenvectors, ¿does exist a class that make somethig like this? Thanks in adavance Carlos Villaseñor
6
2738
by: Guch | last post by:
I'll swictch from Matlab to C++. So I want to find a matrix library of C++, Whitch can process images conveniently as Matlab does. I've googled, and found that Blitz++ and MTL are popular and powerful. I want to know whitch of them fit for image processing better. Or have other choices? Any suggestion whill be appreciated.
2
2828
by: Emacs Row | last post by:
Hello NG, I'm using Numerical Recipes in C++. Now I'm looking for a routine to calculate the eigenvalues of a matrix with *complex* valued entries. The matrix type is Mat_IO_CPLX_DP. So far, I've just found the routines
6
6919
by: lancered | last post by:
Hi dear all, I am using Python2.4.2+NumPy1.0.1 to deal with a parameter estimation problem with the least square methods. During the calculations, I use NumPy package to deal with matrix operations, mostly matrix inversion and trasposition. The dimentions of the matrices used are about 29x19,19x19 and 29x29. During the calculation, I noticed an apparent error of inverion of a 19x19 matrix. Denote this matrix as KK, U=KK^ -1, I found...
18
26361
by: Jedora | last post by:
Hi all, I want to write a C program to compute eigenvalues and eigenvectors. But the matrix is a complex matrix which has all complex numbers. Like this: 5.8751 5.8774 + 1.5423i 2.0818 + 2.8963i 1.8692 + 1.9634i 5.8774 - 1.5423i 6.8258 2.6390 + 2.8255i 2.2955 + 1.9349i 2.0818 - 2.8963i 2.6390 - 2.8255i 3.9534 2.9155 -
4
8093
by: krishnai888 | last post by:
I had already asked this question long back but no one has replied to me..I hope someone replies to me because its very important for me as I am doing my internship. I am currently writing a code involving lot of matrices. At one point I need to calculate the square root of a matrix e.g. A which contains non-zero off-diagonal elements. I searched for a lot of info on net but no algorithm worked. My best bet for finding square root was to find...
2
2811
by: jbd | last post by:
Hi I'm adapting some code I've written using 2d arrays (to represent matrices) to handle large arrays such that double matrix goes to double **matrix and then I'm using malloc. It seems to work fine for part of my program up to where I have to find the matrix transpose at which point it does something I don't understand. I've taken that bit of code out and run it by itself (included below), get the same problem... which is that the input...
0
8886
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9255
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
9168
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9104
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
8090
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
4509
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4780
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3217
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
3
2154
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.