Givens Rotation - Matrix Representation

Matrix Representation

A Givens rotation is represented by a matrix of the form

G(i, j, \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}

where c = cos(θ) and s = sin(θ) appear at the intersections ith and jth rows and columns. That is, the non-zero elements of Givens matrix is given by:

\begin{align} g_{k\, k} &{}= 1 \qquad \text{for} \ k \ne i,\,j\\ g_{i\, i} &{}= c \\ g_{j\, j} &{}= c \\ g_{j\, i} &{}= -s \\ g_{i\, j} &{}= s \qquad \text{for} \ i > j \end{align} (sign of sine switches for j > i)

The product G(i,j,θ)x represents a counterclockwise rotation of the vector x in the (i,j) plane of θ radians, hence the name Givens rotation.

The main use of Givens rotations in numerical linear algebra is to introduce zeros in vectors or matrices. This effect can, for example, 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 often for very sparse matrices they have a lower operation count.

Read more about this topic:  Givens Rotation

Famous quotes containing the word matrix:

    ““The matrix is God?”
    “In a manner of speaking, although it would be more accurate ... to say that the matrix has a God, since this being’s omniscience and omnipotence are assumed to be limited to the matrix.”
    “If it has limits, it isn’t omnipotent.”
    “Exactly.... Cyberspace exists, insofar as it can be said to exist, by virtue of human agency.””
    —William Gibson (b. 1948)