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.

Contents

[edit] Matrix representation

A Givens rotation is represented by a matrix of the form

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}

where c = cos(θ) and s = sin(θ) appear at the intersections ith and kth rows and columns. That is, a Givens rotation matrix is the identity matrix with these substitutions:

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

The product G(i,k,θ)Tx represents a counterclockwise rotation of the vector x in the (i,k) 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, to avoid overflow and underflow, we use a different computation, employing the ratio b/a (which is tan θ) or its reciprocal (Golub & Van Loan 1996). And as Edward Anderson (2000) discovered in improving LAPACK, a previously overlooked numerical consideration is continuity. To achieve this, we required 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 signum function, is an alternative.

[edit] See also

[edit] References