Talk:QR algorithm

From Wikipedia, the free encyclopedia

If i remember it correctly, in general, the complexity is 2*n^3/3 + O(n^2).

"In this crude form the iterations are relatively expensive. This can be mitigated by first bringing the matrix A to upper Hessenberg form with a finite sequence of orthogonal similarity transforms, much like a QR decomposition. For symmetric matrices this replaces a O(n^3) procedure by one that is O(n^2)."

1) You might want to say somewhere that A0:=A :)

2) So, if A is symmetric => procedure costs O(n^2)? Is that also the case for Hermitean matrices?

"If the original matrix is symmetric, then the Hessenberg matrix is also symmetric and thus tridiagonal, and so are all the Ak. This decreases the computational cost of the algorithm because now each QR decomposition is only O(n), not O(n^2)."

Is this not the same assumption as above, ie A is symmetric? So, when is the cost O(n) and when O(n^2)? 131.155.54.18 13:58, 14 November 2005 (UTC), Wilbert Dijkhof

Hoi Wilbert. After consulting Golub & Van Loan, I think the costs are as follows. A single QR-decomposition costs 4/3 n^3 flops in the general case (omitting lower order terms). However, QR-decompositions for Hessenberg matrices cost 6n^2 flops while it costs 10/3 n^3 flops to reduce a matrix to Hessenberg form using Householder transformations. If your matrix is symmetric, then the Hessenberg form is in fact tridiagonal. In this case, it costs 4/3 n^3 flops to bring it in tridiagonal form and I think that every QR-decomposition costs O(n) flops, but I'm not sure about that. Warning: I probably have some constants wrong.

I have no idea how much generalizes to Hermitian matrices. Please do change the article to make it clearer. Groetjes, Jitse Niesen (talk) 15:26, 14 November 2005 (UTC)

Hoi Jitse. Nog steeds in Engeland? I clarified some things a bit, especially about the computational complexity. I also used Golub & Van Loan as source. I hope it's good now. One thing is not clear to me. A general Householder orthogonalization (without using a Hessenberg form) costs 2/3 n^3 (page 148 Golub). This is even less than bringing it to Hessenberg first (5/3 n^3) and then to do a QR decomposition. Is this Hessenberg only used for numerical stability? Wilbert Dijkhof, 131.155.54.18 14:55, 16 November 2005 (UTC)

Nou ja, om precies te zijn, zit ik nog in Schotland. Ze zijn er hier niet zo happig op als je zegt dat Edinburgh in Engeland ligt (net zoals sommigen in Eindhoven niet graag horen dat Eindhoven in Holland ligt).

If all you want to do is computing a simple QR-decomposition, then it is indeed not useful to bring the matrix in Hessenberg form. However, in the QR-algorithm for computing eigenvalues, you have to do many QR-decompositions, each with a cost of 2/3 n^3. In this case, it is better to reduce A to Hessenberg form and incur the 5/3 n^3 cost, because in the next iterations, you can then do the QR-decompositions for O(n^2) cost. Does that make sense? I should stress that numerical linear algebra is not my speciality. In fact, it is one of the fields which I really should know better. -- Jitse Niesen (talk) 23:29, 16 November 2005 (UTC)

[edit] Some possible improvements

Some day this article could use a little fine tuning. To that end, here are a few notes.

The eigenvalues are roots of the characteristic polynomial, so in general we cannot compute them by a fixed predetermined sequence. That's why we use an open-ended iteration to achieve convergence.

This also implies that we cannot directly bring a matrix into upper triangular (or diagonal, for symmetric) form. However, we can use a fixed sequence to bring a matrix into upper Hessenberg (or tridiagonal, for symmetric) form. This gives us a mass of known zeros that will be preserved by the iterations to follow.

Clever as it is that reversing the QR factors effects a similarity transform, it is not at all obvious that doing this repeatedly will produce the convergence we seek. And by itself, it may not.

Success depends critically on use of shifts. That we choose to do the shifts implicitly is a numerical nicety; but decent convergence requires dealing with close eigenvalues somehow. The article really must explain shifting (or link to an explanation).

The most important special case is that of real symmetric matrices. For a real matrix, the characteristic polynomial will have real coefficients; thus any complex eigenvalues occur in complex conjugate pairs. The algorithm may not be able to achieve a real diagonal, and provision must be made for recognizing the 2×2 blocks giving a conjugate pair.

In counting costs, we must distinguish between a QR step, which is iterated an uncertain number of times, and a fixed cost like reduction to upper Hessenberg form. Also the QR factorization gets cheaper as we succeed in isolating roots, because we can ignore more and more of the matrix. Note that for symmetric matrices we can store the matrix as just the diagonal and subdiagonal; this is why the QR factorization is O(n) at worst. Without symmetry, we must touch half the matrix, so we can't beat O(n²). If we can count on a bounded number of iterations per eigenvalue, then the total cost of the iteration phase is n times the cost of an iteration: O(n³) in general, and O(n²) in the symmetric case.

The speed of convergence is one of the most remarkable aspects of the QR algorithm. It was a tremendous improvement over its predecessors. However, today we know that a Jacobi algorithm can give better numeric results, and is more amenable to parallelization. Some mention should be made of these issues, even though QR deservedly remains a workhorse.

Of all these points, the need for an extended discussion of shifting seems most urgent. --KSmrq^T 13:13, 19 August 2006 (UTC)

[edit] Termination

Is it possible to decide if this algorithm terminates which means the given matrix has actually eigenvalues? If so it should be mentioned here I suppose. Nulli 10:28, 15 November 2006 (UTC)

[edit] QR decomposition

Why don't we merge this page in the QR decomposition one, and then link this one to QR decomposition ?

--Fbianco 22:14, 15 April 2007 (UTC)

QR decomposition should have a link to here, but they are different. QR iteration (this page) uses QR decomposition to find eigenvalues.