GIVENS ROTATIONS

Givens rotations annihilate off-diagonal matrix elements. They are often used in solving the symmetric eigenvalue problem, and have received greater attention recently because they lend themselves well to a parallel implementation.

The basic idea in Givens rotations is to annihilate a particular off-diagonal element of a matrix (and its symmetric pair). We can zero the elements a_pq and a_qp of matrix A by applying a coordinate rotation given by:

$$\pmatrix{b_{pp}&0\cr 0&b_{qq}\cr}= \pmatrix{cos\theta&sin\t... ...}\cr} \pmatrix{cos\theta&sin\theta\cr -sin\theta&cos\theta\cr}$$ (1)

Effectively we have rotated the coordinate system by an angle $\theta$,and chosen $\theta$ such that in the new coordinate system the desired off-diagonal elements will be zero. The diagonal elements a_pp and a_qq are modified by this transformation.

Golub and Van Loan (1989) show that $\theta$ is given by:

$$\theta = {{a_{qq} - a_{pp}}\over{2 a_{pq}}}.$$ (2)

Following Press et al (1986), after rotation the new values are given by:

b_pp = a_pp - t a_pq

b_qq = a_pp + t a_pq,

where

$$t = {{sgn(\theta) \over {\vert\theta\vert + \sqrt{\theta^{2} + 1}}}}.$$ (5)

On a larger scale, the operation that we perform on the full matrix A is:

$$B = J(\theta)^{T} A J$$ (6)

where $J(\theta)$ is given by:

$$J(\theta) = {\pmatrix{1&\ldots&0&\ldots&0&\ldots&0\cr \vdot... ...ots&&\vdots&\ddots&\vdots\cr 0&\ldots&0&\dots&0&\ldots&1\cr}}.$$ (7)

This technique is one method traditionally used to find the eigenvalues and eigenvectors of a matrix. If we annihilate all the off-diagonal elements, we are left with a diagonal matrix B that contains the eigenvalues of A. The rotation matrices $J(\theta)$ needed to perform the annihilations, when cascaded together, yield the eigenvectors of the matrix A. When Givens rotations are used in this way to diagonalize a matrix, the method is known as a Jacobi transformation (unrelated to the Jacobi iterative scheme I mentioned earlier). Givens rotations are also known as Jacobi rotations for this reason.

This method of diagonalizing a matrix is obviously quite expensive in the general case, since there are (n-1)*(n-2)/2 annihilations to perform for an nxn matrix. But in our case, A is very sparse, and we want only to attack the outer diagonals of Table (1), leaving a tridiagonal system that we can solve using traditional methods. The cost should be quite small.

It would be straightforward if this operation zeroed the two off-diagonal elements and left the rest of the matrix unchanged. Unfortunately this is not the case. When we pre-multiply A by $J(\theta)^{T}$ and post-multiply by $J(\theta)$,what is modified is not just the two diagonal and two off-diagonal elements we are interested in, but the whole two rows and two columns that contain these elements.

In other words, as we move through the matrix, annihilating off-diagonal elements, we create non-zero elements elsewhere, and occasionally fill in previously-created zeros. For this reason, the scheme is not direct but iterative. One pass through the matrix increases the diagonal dominance, but leaves some artifacts. Additional passes gradually knock down these artifacts, and at some point everything off the diagonal is small enough that it can be ignored. Press et al. suggest 6-10 passes are needed for the general case of diagonalizing a matrix. The action of the method is best illustrated by an example, as in the following section.

The method lends itself well to a parallel implementation because a given rotation modifies only two rows or two columns of the matrix. If only one column or row were to be modified in each rotation, we would need only two passes - one for modifying the rows and one for the columns - in order to attack an entire diagonal in parallel. The fact that two rows or columns are modified simultaneously means that four passes (two for rows, two for columns) are required. This is still very few, and suggests that parallel implementations should be extremely fast.