next up previous index
Next: The Householder Reduction Up: Eigensystems Previous: Example Code

The Householder-QR/QL Algorithm

The Jacobi rotations method is not too bad. It usually converges in between 18 N3 to 30 N3 operations. There is no way to get out of the N3 dependence, but the coefficient can be reduced to $\frac{4}{3} N^3$ (for diagonalization without eigenvectors), and that can be a very considerable saving, especially if N is very large.

The most efficient known technique for finding eigenvalues and eigenvectors of a symmetric matrix is the combination of the Householder reduction, which reduces a symmetric real matrix to a tridiagonal form, followed by the so called QR or a QL algorithm that can diagonalize a tridiagonal matrix within about 30 N2 steps without eigenvectors. If eigenvectors are required then the number of operations grows to 3 N3.

The QR or a QL method is still an iterative method. But the orthogonal transformation employed preserves:

So zeros stay zeroed. And this means that there are only N-2 off-diagonal elements to kill.

The Householder reduction on the other hand is a finite procedure, i.e., not an iterative one at all. A symmetric matrix can be reduced to a tridiagonal form within a finite well defined number of steps: N-2 orthogonal transformations.



 
next up previous index
Next: The Householder Reduction Up: Eigensystems Previous: Example Code
Zdzislaw Meglicki
2001-02-26