1
$\begingroup$

You compute A = QR by using givens rotations, and use the QR algorithm for finding eigenvalues of A. The process of finding eigenvalues can be sped up by transforming A to a Hessenberg matrix (by using givens).

I'm guessing using a Hessenberg matrix is more efficient because of the fact that for every QR factorization you now do, you have to do less givens rotations? Correct me on this if I'm wrong.

Now onto the question: Why don't we transform A to an upper triangular matrix to begin with? Why stop at a Hessenberg form?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Yes, in Hessenbergform, you only need ~$n$ Givens-Rotations per QR step, in full form that requires ~$n^2/2$ rotations.

It is not possible to just get the triangular form. Would be nice, since that would have the eigenvalues directly on the diagonal.

$\endgroup$
5
  • $\begingroup$ Forgive me for my ignorance, but why can't we just keep doing Givens transformations to obtain the upper triangular format? Why can't we do better than a Hessenberg matrix? When decomposing A into Q and R, the basic algorithm that uses Givens rotations also just keeps transforming A into R, an upper triangular matrix. And finally uses the sequence of Givens matrices G_ij to construct Q. $\endgroup$
    – xrdty
    Commented Jan 21, 2016 at 23:44
  • 1
    $\begingroup$ Note that the next matrix in the QR algorithm is $A_+=RQ=Q^TAQ$. What the Givens rotation (or Householder reflection) on the left sets to zero, the same operation after application from the right can disturb. The best you can get in one step is Hessenberg. $\endgroup$
    – Lutz Lehmann
    Commented Jan 21, 2016 at 23:47
  • $\begingroup$ Aha, I thought we transformed A to its Hessenberg equivalent prior to running the QR algorithm. So it is actually between every step of the QR algorithm that its converted again to its Hessenberg form? $\endgroup$
    – xrdty
    Commented Jan 21, 2016 at 23:56
  • $\begingroup$ No, your prior information is right. The QR steps preserve the Hessenberg form. So you have one effort of O(n²) and then O(n) per step versus O(n²) in every step. $\endgroup$
    – Lutz Lehmann
    Commented Jan 22, 2016 at 8:49
  • $\begingroup$ Ah! Your last comment combined with your first comment makes it clear to me. Thanks! $\endgroup$
    – xrdty
    Commented Jan 22, 2016 at 12:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .