1
$\begingroup$

I'm interested in calculating the roots of an 11th degree polynom. To do so, I calculated the 10x10 companion matrix which eigenvalues are the roots of the polynom. Now, the eigenvalues could be real or complex and in my code, I just need real ones. Is there a way to find the real eigenvalues only of an upper Hessenberg matrix (companion matrix) using iterations of the QR algorithm?

I tried this: Let A be our upper Hessenberg matrix

M=A
for i=1:100
[Q,R]=qr(M);
M=R*Q;
end

diag(M) will converge to eig(A) if A is symmetric, if not real eigenvalues exist but complex ones dosen't. I just need real eigenvalues but how to distinguish in diag(M) values that the entry correspond to a real eigenvalue?

$\endgroup$
  • $\begingroup$ Sure, just start applying the $QR$ algorithm. It'll converge fairly nicely if you start with something upper-hessenberg. $\endgroup$ – Omnomnomnom Jun 30 '15 at 0:35
0
$\begingroup$

First, there is no advantage to trying to compute only the real eigenvalues versus just computing them all; they could all be real or all be complex.

Second, the QR algorithm as you've written it converges extremely slowly compared to state-of-the-art implicitly shifted Hessenberg QR. If you use eig() in Matlab, it will use the faster algorithm and almost certainly be faster than your qr in a loop.

$\endgroup$
  • $\begingroup$ the whole point of the Matlab QR is that it puts the matrix into Hessenberg form. OP is starting with such a matrix $\endgroup$ – Omnomnomnom Jun 30 '15 at 1:00
  • $\begingroup$ The problem is that i'm porting a Matlab code to gpu, and I need to compute roots of several polynoms in parallel..The rest of the code works only with real roots..Is it possible to implement the shifted QR and retrieve real eigenvalues? $\endgroup$ – Didon Jun 30 '15 at 1:10
  • $\begingroup$ And I'm sure the Matlab algorithm will take advantage of the fact that it is already upper Hessenberg, since I know that the Lapack code does it. $\endgroup$ – Victor Liu Jun 30 '15 at 1:49
  • $\begingroup$ Check out the MAGMA project that aims to implement linear algebra on the GPU. Edit: MAGMA doesn't support non-symmetric problems. Let me look up this other thing... $\endgroup$ – Victor Liu Jun 30 '15 at 1:50
  • $\begingroup$ Check out this paper. $\endgroup$ – Victor Liu Jun 30 '15 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.