Finding eigenvalues with QR method

[Thor90]

Hi, I am trying to solve the problem of finding eigenvalus for a general square symmetric matrix with the QR algorithm.
I have understood that this task is much easier if the matrix is in an Hessemberg form, so I have implemented a function that does that with the Housholder method, but I can't understand how to find the qr decomposition of the given matrix in a useful computational way. The algebric algorithm is clear for me but I don't know how to reproduce it in C since I'm not understanding how to work with the decomposition process.
Can someone explain this for me?
That is, given the original matrix A in an Hessemberg form, how can I find the two matrices Q (orthogonal) and R (upper triangular) so that A=Q*R?

 

[Dr. Courtney]

Test your code with matrices that have a known form at each step to see which step is not working.

 

[Thor90]

There is nothing that doesn't work with my program. I am simply not understanding how to decompose a matrix this way in C (I am a physics not a computer scientist), that means in an iterative way. Where can I find an algorithm to decompose a matrix like this? How does the Hessemberg form come in help?

 

[SteamKing]

There is nothing that doesn't work with my program. I am simply not understanding how to decompose a matrix this way in C (I am a physics not a computer scientist), that means in an iterative way. Where can I find an algorithm to decompose a matrix like this? How does the Hessemberg form come in help?

It's Hessenberg, not Hessemberg.

There's any number of web pages describing QR and using QR to find eigenvalues. You could take a look at the routines in LAPACK which are written in Fortran.
You can either use a C wrapper for the LAPACK and run it with your code, or you can use a Fortran-to-C translation called CLAPACK.

http://www.netlib.org/clapack/

The netlib is a good source for all sorts of algorithms of this nature.

This page has a description of the QR method:

http://mathfaculty.fullerton.edu/mathews/n2003/QRMethodMod.html

In any event, you can find a lot of information about these algorithms, along with actual code, by doing a Google search. This saves a lot of time.

I wouldn't write a routine from scratch unless it was absolutely, positively necessary.

 

[Thor90]

It's Hessenberg, not Hessemberg.

Sorry for the mistake

There's any number of web pages describing QR and using QR to find eigenvalues. You could take a look at the routines in LAPACK which are written in Fortran.

I know that, the fact is that is my first time doing this kind of things and I have no idea how to use/install lapack, but if it's the only way I will try to do that.

This page has a description of the QR method:

http://mathfaculty.fullerton.edu/mathews/n2003/QRMethodMod.html

In any event, you can find a lot of information about these algorithms, along with actual code, by doing a Google search. This saves a lot of time.

I have already done my search but as I said before I am not an expert and I am not able to understandand how to do this routine if only a code is posted without any explanation.
Anyway the page you linked me only has mathematica subrutines. I agree that it would be much easier to do with mathematica but I need to use C++ to solve this problem.
And beside that in every page I found about the qr algorithm anyone seems to take as granted that I know how to decompose a matrix in a product of Q and R, which is not.

 

[SteamKing]

Well, did you check out CLAPACK? There are versions of these routines translated into C++.

As far as the QR page is concerned, there is some pseudocode there along with the Mathematica. If you are going to write code, you must develop a rudimentary knowledge of other programming languages in order to understand the structure of how routines written in them work.

As I mentioned, the page I linked to about QR was one of many. Google "QR algorithm" to get other pages so that you can understand how QR works, then you can narrow your search to eigenvalue specific pages.

BTW, I think most eigenvalue finding routines use the Singular Value Decomposition method over QR, although the two methods use similar features from linear algebra.

I also recommend that you get a copy of Golub and van Loan's "Matrix Computations" if you want to figure out the various algorithms and how to code them.