Finding eigenvalues with QR method

Click For Summary

Discussion Overview

The discussion revolves around the process of finding eigenvalues of a general square symmetric matrix using the QR algorithm, with a focus on the computational implementation in C. Participants explore the QR decomposition and its relation to the Hessenberg form of matrices, as well as resources for coding these algorithms.

Discussion Character

  • Technical explanation
  • Debate/contested
  • Homework-related

Main Points Raised

  • One participant seeks clarification on how to compute the QR decomposition of a matrix in C, specifically after transforming it into Hessenberg form using the Householder method.
  • Another participant suggests testing the code with known matrices to identify issues in the implementation.
  • A participant expresses frustration over their lack of understanding of the decomposition process in C and requests an algorithm for this task.
  • There is a correction regarding the spelling of "Hessenberg," with a participant emphasizing the correct term.
  • Several participants recommend exploring LAPACK and CLAPACK for existing routines and algorithms related to QR decomposition and eigenvalue computation.
  • One participant notes that they are unfamiliar with using LAPACK and expresses a willingness to learn, despite their inexperience.
  • Another participant mentions that many resources assume prior knowledge of matrix decomposition, which they find challenging.
  • There is a suggestion that most eigenvalue finding routines may prefer Singular Value Decomposition (SVD) over QR, though both methods share similarities.
  • A recommendation is made to consult "Matrix Computations" by Golub and van Loan for further understanding of the algorithms involved.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the best approach to implement the QR algorithm in C, and multiple viewpoints regarding the use of existing libraries and the understanding of the decomposition process remain evident.

Contextual Notes

Participants express varying levels of familiarity with programming and mathematical concepts, leading to discussions that highlight assumptions about prior knowledge. There are also references to specific resources that may not be universally accessible or understandable to all participants.

Thor90
Messages
9
Reaction score
0
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?
 
Technology news on Phys.org
Test your code with matrices that have a known form at each step to see which step is not working.
 
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?
 
Thor90 said:
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.
 
SteamKing said:
It's Hessenberg, not Hessemberg.

Sorry for the mistake

SteamKing said:
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.

SteamKing said:
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.
 
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.
 
  • Like
Likes   Reactions: Thor90

Similar threads

Undergrad Proving SL_2(C) Homeomorphic to SU(2)xT & Simple Connectedness
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Can one find a matrix that's 'unique' to a collection of eigenvectors?
  • · Replies 33 ·
2
Replies
33
Views
3K
How to use QR decomposition to find eigenvalues?
  • · Replies 1 ·
Replies
1
Views
4K
Graduate The eigenvalue power method for quantum problems
  • · Replies 2 ·
Replies
2
Views
2K
Graduate Can't find eigenvalues for s-wave superconductor
  • · Replies 1 ·
Replies
1
Views
1K
Graduate Eigenvalues/eigenvectors using householder and QR
  • · Replies 5 ·
Replies
5
Views
5K
Challenge: Find the minimum amount of draws possible for a list of integers
  • · Replies 9 ·
Replies
9
Views
3K
Undergrad Getting eigenvalues of an arbitrary matrix with programming
  • · Replies 1 ·
Replies
1
Views
2K
Fortran I can't find a small bug in this Fortran code
  • · Replies 2 ·
Replies
2
Views
1K
Engineering How do I find the transition matrix of this dynamic system?
  • · Replies 18 ·
Replies
18
Views
4K