Talk:QR algorithm

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