A Givens rotation is represented by a
matrix of the form
where c = cos θ and s = sin θ appear at the intersections ith and jth rows and columns. That is, for fixed i>j, the non-zero elements of Givens matrix are given by:
The product G(i, j, θ)x represents a counterclockwise rotation of the
vectorx in the (i, j) plane of θ radians, hence the name Givens rotation.
The main use of Givens rotations in
numerical linear algebra is to transform vectors or matrices into a special form with zeros in certain coefficients. 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.
Stable calculation
When a Givens rotation matrix, G(i, j, θ), multiplies another matrix, A, from the left, G A, only rows i and j of A are affected. Thus we restrict attention to the following counterclockwise problem. Given a and b, find c = cos θ and s = sin θ such that
where is the length of the vector .
Explicit calculation of θ is rarely necessary or desirable. Instead we directly seek c and s. An obvious solution would be
However, the computation for r may
overflow or underflow. An alternative formulation avoiding this problem (
Golub & Van Loan 1996, §5.1.8) is implemented as the
hypot function in many programming languages.
The following Fortran code is a minimalistic implementation of Givens rotation for real numbers. If the input values 'a' or 'b' are frequently zero, the code may be optimized to handle these cases as presented
here.
Furthermore, as Edward Anderson discovered in improving
LAPACK, a previously overlooked numerical consideration is continuity. To achieve this, we require r to be positive.[2] The following
MATLAB/
GNU Octave code illustrates the algorithm.
function[c, s, r] = givens_rotation(a, b)ifb==0;c=sign(a);if(c==0);c=1.0;% Unlike other languages, MatLab's sign function returns 0 on input 0.end;s=0;r=abs(a);elseifa==0;c=0;s=-sign(b);r=abs(b);elseifabs(a)>abs(b);t=b/a;u=sign(a)*sqrt(1+t*t);c=1/u;s=-c*t;r=a*u;elset=a/b;u=sign(b)*sqrt(1+t*t);s=-1/u;c=t/u;r=b*u;endend
The
IEEE 754copysign(x,y) function, provides a safe and cheap way to copy the sign of y to x. If that is not available, |x|⋅sgn(y), using the
abs and
sgn functions, is an alternative as done above.
Triangularization
Given the following 3×3 Matrix:
two iterations of the Givens rotation (note that the Givens rotation algorithm used here differs slightly from above) yield an upper
triangular matrix in order to compute the
QR decomposition.
In order to form the desired matrix, zeroing elements (2,1) and (3,2) is required; element (2,1) is zeroed first, using a rotation matrix of:
The following matrix multiplication results:
where
Using these values for c and s and performing the matrix multiplication above yields A2:
Zeroing element (3,2) finishes off the process. Using the same idea as before, the rotation matrix is:
Afterwards, the following matrix multiplication is:
where
Using these values for c and s and performing the multiplications results in A3:
This new matrix A3 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:
Performing this matrix multiplication yields:
This completes two iterations of the Givens Rotation and calculating the
QR decomposition can now be done.
Complex matrices
Another method can extend Givens rotations to complex matrices. A diagonal matrix whose diagonal elements have unit magnitudes but arbitrary phases is unitary. Let A be a matrix for which it is desired to make the ji element be zero using the rows and columns i and j>i. Let D be a diagonal matrix whose diagonal elements are one except the ii and jj diagonal elements which also have unit magnitude but have phases which are to be determined. The phases of the ii and jj elements of D can be chosen so as to make the ii and ji elements of the product matrix D A be real. Then a Givens rotation G can be chosen using the i and j>i rows and columns so as to make the ji element of the product matrix G D A be zero. Since a product of unitary matrices is unitary, the product matrix G D is unitary and so is any product of such matrix pair products.
In Clifford algebra
In
Clifford algebra and its child structures such as
geometric algebra, rotations are represented by
bivectors. Givens rotations are represented by the exterior product of the basis vectors. Given any pair of basis vectors Givens rotations bivectors are:
When rotations are performed in the right order, the values of the rotation angles of the final frame will be equal to the
Euler angles of the final frame in the corresponding convention. For example, an operator transforms the basis of the space into a frame with angles roll, pitch and yaw in the
Tait–Bryan conventionz-x-y (convention in which the line of nodes is perpendicular to z and Y axes, also named Y-X′-Z″).
The meaning of the composition of two Givens rotations g ∘ f is an operator that transforms vectors first by f and then by g, being f and g rotations about one axis of basis of the space. This is similar to the
extrinsic rotation equivalence for Euler angles.
Table of composed rotations
The following table shows the three Givens rotations equivalent to the different Euler angles conventions using extrinsic composition (composition of rotations about the basis axes) of
active rotations and the right-handed rule for the positive sign of the angles.
The notation has been simplified in such a way that c1 means cos θ1 and s2 means sin θ2). The subindexes of the angles are the order in which they are applied using extrinsic composition (1 for intrinsic rotation, 2 for nutation, 3 for precession)
As rotations are applied just in the opposite order of the
Euler angles table of rotations, this table is the same but swapping indexes 1 and 3 in the angles associated with the corresponding entry. An entry like zxy means to apply first the y rotation, then x, and finally z, in the basis axes.
All the compositions assume the right hand convention for the matrices that are multiplied, yielding the following results.
^The rotation matrix immediately below is not a Givens rotation. The matrix immediately below respects the right-hand rule and is this usual matrix one sees in Computer Graphics; however, a Givens rotation is simply a matrix as defined in the
Matrix representation section above and does not necessarily respect the right-hand rule. The below matrix is actually the Givens rotation through an angle of -.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007),
"Section 11.3.1. Givens Method", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press,
ISBN978-0-521-88068-8, archived from
the original on 2011-08-11, retrieved 2011-08-13