[Math] Why does Givens rotation avoid iteration and Jacobi rotation doesn’t in case of reducing a symmetric matrix to tridiagonal

eigenvalues-eigenvectorslinear algebramatrices

I am currently implementing symmetric matrix reduction to tridiagonal.
I read that Givens rotation avoids iteration when it is used for reducing a matrix to tridiagonal whereas Jacobi rotation is iterative. Givens rotation try to annihilate the element $a_{i-1j}$ by a rotation in $ij-$plane and Jacobi rotation try to annihilate the element $a_{ij}$ by a rotation in $ij-$plane. But just because of that, how can Givens rotation avoid iteration as both use same equations?

$a^{'}_{rp}=ca_{rp} – sa_{rq}$

$ a^{'}_{rq}=ca_{rp} + sa_{rq}$

$ a^{'}_{pp}=c^{2}a_{pp}+s^{2}a_{qq}-2sca_{pq}$

$a^{'}_qq=s^{2}a_{pp}+c^{2}a_{qq}+2sca_{pq}$

$a^{'}_{pq}=(c^{2}-s^{2})a_{pq}+sc(a_{pp}-a_{qq})$

Now in Jacobi rotation , they try to zero out $a^{'}_{pq}$ and in Givens rotation they try to zero out $a^{'}_{p-1q}$ i.e.,$ a^{'}_{rq}$.

Best Answer

The fundamental difference is that the Jacobi method attempts to reduce the matrix to diagonal form, and successive rotations undo previously set zeros, but the off-diagonal elements successively get smaller and smaller (thus it is an "iterative" method).

The sequence of Givens rotations tries to do something easier: It reduces the matrix to tridiagonal form. It can do this in a finite number of steps. If you still need the eigenvalues and eigenvectors, you can work with that tridiagonal form to find eigenvalues; that calculation still requires iteration, but if you are interested only in a small number of eigenvalues (say the largest ones) that may be a reasonable approach.

Of course, if your goal is explicitly just reduction to tridiagonal, then Givens rotation is clearly superior to the iteration of Jacobi rotations. However, for that purpose, the Householder algorithm, in which each transformation annihilates part of a whole column and the corresponding row, is clearly superior to the Givens method (just as stable, and twice as efficient). See sections 11.1 and 11.3 of Numerical Recipes for details.

Related Question