Givens rotation

From Wikipedia, the free encyclopedia

In numerical linear algebra, a Givens rotation is a rotation in the plane spanned by two coordinates axes. Givens rotations are named after Wallace Givens who introduced them to numerical analysts in the 1950s while he was working at Argonne National Laboratory.

[edit] 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, a Givens rotation matrix is the identity matrix with these substitutions:

$\begin{align} g_{i\, i} &{}= c \\ g_{j\, j} &{}= c \\ g_{i\, j} &{}= s \\ g_{j\, i} &{}= -s \end{align}$

The product G(i,j,θ)^Tx 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.

[edit] Stable calculation

When a Givens rotation matrix, G(i,k,θ), is multiplied times another matrix, A, from the left, GA, only rows i and k of A are affected. Thus we restrict attention to the following problem. Given a and b, find c = cos θ and s = sin θ such that

$\begin{bmatrix} c & s \\ -s & c \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} r \\ 0 \end{bmatrix} .$

Explicit calculation of θ is rarely necessary or desirable. Instead we directly seek c, s, and r. An obvious solution would be

$\begin{align} r &{}\larr \sqrt{a^2 + b^2} \\ c &{}\larr a / r \\ s &{}\larr b / r. \end{align}$

However, the computation for r may overflow or underflow. An alternative formulation which does not overflow if |b| ≥ |a| > 0 is t ← −a / b, s ← 1 / sqrt(1 + t²), c ← st; similar reformulations cover the other cases (Golub & Van Loan 1996, §5.1.8). Another possibility is to use the hypot function.

Furthermore, as Anderson (2000) discovered in improving LAPACK, a previously overlooked numerical consideration is continuity. To achieve this, we require r to be positive.

if (b = 0) then {c ← copysign(1,a); s ← 0; r ← abs(a)}
else if (a = 0) then {c ← 0; s ← copysign(1,b); r ← abs(b)}
else if (abs(b) > abs(a)) then
  t ← a/b
  u ← copysign(sqrt(1+t*t),b)
  s ← 1/u
  c ← s*t
  r ← b*u
else
  t ← b/a
  u ← copysign(sqrt(1+t*t),a)
  c ← 1/u
  s ← c*t
  r ← a*u

This is written in terms of the IEEE 754r copysign(x,y) function, which provides a safe and cheap way to copy the sign of y to x. If that is not available, x*sgn(y), using the sign function, is an alternative.

[edit] Example

Given the following 3x3 Matrix, perform two iterations of the Given's Rotation to bring the matrix to an upper Triangular matrix in order to compute the QR decomposition.

$A = \begin{bmatrix} 6 & 5 & 0 \\ 5 & 1 & 4 \\ 0 & 4 & 3 \\ \end{bmatrix}$

In order to form the desired matrix, we must zero elements (2,1) and (3,2). We first select element (2,1) to zero. Using a rotation matrix of:

$G_{1} = \begin{bmatrix} c & s & 0 \\ -s & c & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}$

We have the following matrix multiplication:

$\begin{bmatrix} c & s & 0 \\ -s & c & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 6 & 5 & 0 \\ 5 & 1 & 4 \\ 0 & 4 & 3 \\ \end{bmatrix}$

Where:

$\begin{align} r &{}= \sqrt{6^2 + 5^2} \\ c &{}= 6 / r\\ s &{}= 5 / r \end{align}$

Plugging in these values for c and s and performing the matrix multiplication above yields a new A of:

$A = \begin{bmatrix} 7.8102 & 4.4812 & 2.5602 \\ 0 & -2.4328 & 3.0728 \\ 0 & 4 & 3 \\ \end{bmatrix}$

We now want to zero element (3,2) to finish off the process. Using the same idea as before, we have a rotation matrix of:

$G_{2} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & c & s \\ 0 & -s & c \\ \end{bmatrix}$

We are presented with the following matrix multiplication:

$\begin{bmatrix} 1 & 0 & 0 \\ 0 & c & s \\ 0 & -s & c \\ \end{bmatrix} \begin{bmatrix} 7.8102 & 4.4812 & 2.5602 \\ 0 & -2.4328 & 3.0728 \\ 0 & 4 & 3 \\ \end{bmatrix}$

Where:

$\begin{align} r &{}= \sqrt{-2.4328^2 + 4^2} \\ c &{}= -2.4328 / r\\ s &{}= 4 / r \end{align}$

Plugging in these values for c and s and performing the multiplications gives us a new matrix of:

$R = \begin{bmatrix} 7.8102 & 4.4812 & 2.5602 \\ 0 & 4.6818 & 0.9664 \\ 0 & 0 & -4.1843 \\ \end{bmatrix}$

This new matrix R is the upper triangular matrix needed to perform an iteration of the QR decomposition. Q is now formed using the transpose of the rotation matrices in the following manner:

$Q = G_{1}^T * G_{2}^T$