Givens rotation

From Free net encyclopedia

In mathematics, a Givens rotation is a matrix of the form

<math>G(i, k, \theta) =

      \begin{bmatrix}   1   & \cdots &    0   & \cdots &    0   & \cdots &    0   \\
                     \vdots & \ddots & \vdots &        & \vdots &        & \vdots \\
                        0   & \cdots &    c   & \cdots &    s   & \cdots &    0   \\
                     \vdots &        & \vdots & \ddots & \vdots &        & \vdots \\
                        0   & \cdots &   -s   & \cdots &    c   & \cdots &    0   \\
                     \vdots &        & \vdots &        & \vdots & \ddots & \vdots \\
                        0   & \cdots &    0   & \cdots &    0   & \cdots &    1
      \end{bmatrix}</math>

where c = cos(θ) and s = sin(θ) appear in the ith / kth row and column, respectively. More formally,

<math>G(i, k, \theta)_{j, \ell} = \begin{cases} \cos\theta & \mbox{ if } j = i, \ell = i \mbox{ or } j = k, \ell = k, \\

                                                     \sin\theta & \mbox{ if } j = i, \ell = k, \\
                                                    -\sin\theta & \mbox{ if } j = k, \ell = i, \\
                                                     1          & \mbox{ if } j = \ell, \\
                                                     0          & \mbox{ otherwise.}
      \end{cases}</math>

The product <math>G(i, k, \theta)^Tx</math> represents a counter-clockwise rotation of the vector x in the (i, k) plane about θ radians, hence the name Givens rotation.

The main use of Givens rotations in numerical linear algebra is to introduce zeros in vectors/matrices. This effect can e.g. be employed for computing the QR decomposition of a matrix; one advantage over Householder transformations is that they can easily be parallelised, and another is that for many very sparse matrices they have lower operation count.

References

• Gene H. Golub and Charles F. van Loan, Matrix Computations, 2nd edn., The Johns Hopkins University Press, 1989.de:Givens-Rotation