Givens rotation
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
.
of the form
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:
(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 transformation
s is that they can easily be parallelised, and another is that often for very sparse matrices they have a lower operation count.
Explicit calculation of θ is rarely necessary or desirable. Instead we directly seek c, s, and r. An obvious solution would be
However, the computation for r may overflow
or underflow. An alternative formulation avoiding this problem is implemented as the hypot
function in many programming languages .
Furthermore, as 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 754 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.
in order to compute the QR decomposition
.
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:
We have the following matrix multiplication:
Where:
Plugging in these values for c and s and performing the matrix multiplication above yields a new A of:
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:
We are presented with the following matrix multiplication:
Where:
Plugging in these values for c and s and performing the multiplications gives us a new matrix of:
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:
Performing this matrix multiplication yields:
This completes two iterations of the Givens Rotation and calculating the QR decomposition
can now be done.
rotations are represented by bivectors. Givens rotations are represented by the external product of the basis vectors. Given any pair of basis vectors
Givens rotations bivectors are:
Their action on any vector is written :
where :
There are three Givens rotations in dimension 3:
Given that they are endomorphism
s they can be composed with each other as many times as desired, keeping in mind that g ∘ f ≠ f ∘ g.
These three Givens rotations composed can generate any rotation matrix. This means that they can transform the basis of the space to any other frame
in the space.
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 convention z-x-y (convention in which the line of nodes is perpendicular to z and Y axes, also named Y-X’-Z’’).
For the same reason, any rotation matrix in 3D can be decomposed in a product of three of these rotations
.
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.
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.
Numerical linear algebra
Numerical linear algebra is the study of algorithms for performing linear algebra computations, most notably matrix operations, on computers. It is often a fundamental part of engineering and computational science problems, such as image and signal processing, Telecommunication, computational...
, a Givens rotation is a rotation
Rotation (mathematics)
In geometry and linear algebra, a rotation is a transformation in a plane or in space that describes the motion of a rigid body around a fixed point. A rotation is different from a translation, which has no fixed points, and from a reflection, which "flips" the bodies it is transforming...
in the plane spanned by two coordinates axes. Givens rotations are named after Wallace Givens
Wallace Givens
James Wallace Givens, Jr. was a mathematician and a pioneer in computer science. He is the eponym of the well-known Givens rotations...
, who introduced them to numerical analysts in the 1950s while he was working at Argonne National Laboratory
Argonne National Laboratory
Argonne National Laboratory is the first science and engineering research national laboratory in the United States, receiving this designation on July 1, 1946. It is the largest national laboratory by size and scope in the Midwest...
.
Matrix representation
A Givens rotation is represented by a matrixMatrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
of the form
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:
(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
Numerical linear algebra
Numerical linear algebra is the study of algorithms for performing linear algebra computations, most notably matrix operations, on computers. It is often a fundamental part of engineering and computational science problems, such as image and signal processing, Telecommunication, computational...
is to introduce zeros in vectors or matrices.
This effect can, for example, be employed for computing the QR decomposition
QR decomposition
In linear algebra, a QR decomposition of a matrix is a decomposition of a matrix A into a product A=QR of an orthogonal matrix Q and an upper triangular matrix R...
of a matrix. One advantage over Householder transformation
Householder transformation
In linear algebra, a Householder transformation is a linear transformation that describes a reflection about a plane or hyperplane containing the origin. Householder transformations are widely used in numerical linear algebra, to perform QR decompositions and in the first step of the QR algorithm...
s 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,k,θ), multiplies 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 thatExplicit calculation of θ is rarely necessary or desirable. Instead we directly seek c, s, and r. An obvious solution would be
However, the computation for r may overflow
Arithmetic overflow
The term arithmetic overflow or simply overflow has the following meanings.# In a computer, the condition that occurs when a calculation produces a result that is greater in magnitude than that which a given register or storage location can store or represent.# In a computer, the amount by which a...
or underflow. An alternative formulation avoiding this problem is implemented as the hypot
Hypot
Hypot is a mathematical function defined to calculate the length of the hypotenuse of a right-angle triangle. It was designed to avoid errors arising due to limited-precision calculations performed on computers.-Motivation and usage:...
function in many programming languages .
Furthermore, as discovered in improving LAPACK
LAPACK
-External links:* : a modern replacement for PLAPACK and ScaLAPACK* on Netlib.org* * * : a modern replacement for LAPACK that is MultiGPU ready* on Sourceforge.net* * optimized LAPACK for Solaris OS on SPARC/x86/x64 and Linux* * *...
, 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 754 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
Sign function
In mathematics, the sign function is an odd mathematical function that extracts the sign of a real number. To avoid confusion with the sine function, this function is often called the signum function ....
, is an alternative.
Triangularization
Given the following 3x3 Matrix, perform two iterations of the Given's Rotation to bring the matrix to an upper Triangular matrixTriangular matrix
In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix where either all the entries below or all the entries above the main diagonal are zero...
in order to compute the QR decomposition
QR decomposition
In linear algebra, a QR decomposition of a matrix is a decomposition of a matrix A into a product A=QR of an orthogonal matrix Q and an upper triangular matrix R...
.
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:
We have the following matrix multiplication:
Where:
Plugging in these values for c and s and performing the matrix multiplication above yields a new A of:
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:
We are presented with the following matrix multiplication:
Where:
Plugging in these values for c and s and performing the multiplications gives us a new matrix of:
This new matrix R is the upper triangular matrix needed to perform an iteration of the QR decomposition
QR decomposition
In linear algebra, a QR decomposition of a matrix is a decomposition of a matrix A into a product A=QR of an orthogonal matrix Q and an upper triangular matrix R...
. 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
QR decomposition
In linear algebra, a QR decomposition of a matrix is a decomposition of a matrix A into a product A=QR of an orthogonal matrix Q and an upper triangular matrix R...
can now be done.
Givens rotations in Clifford Algebras
In Clifford algebras and its child structures like geometric algebraGeometric algebra
Geometric algebra , together with the associated Geometric calculus, provides a comprehensive alternative approach to the algebraic representation of classical, computational and relativistic geometry. GA now finds application in all of physics, in graphics and in robotics...
rotations are represented by bivectors. Givens rotations are represented by the external product of the basis vectors. Given any pair of basis vectors
Givens rotations bivectors are:Their action on any vector is written :
where :
Dimension 3
- See also Euler anglesEuler anglesThe Euler angles are three angles introduced by Leonhard Euler to describe the orientation of a rigid body. To describe such an orientation in 3-dimensional Euclidean space three parameters are required...
There are three Givens rotations in dimension 3:
Given that they are endomorphism
Endomorphism
In mathematics, an endomorphism is a morphism from a mathematical object to itself. For example, an endomorphism of a vector space V is a linear map ƒ: V → V, and an endomorphism of a group G is a group homomorphism ƒ: G → G. In general, we can talk about...
s they can be composed with each other as many times as desired, keeping in mind that g ∘ f ≠ f ∘ g.
These three Givens rotations composed can generate any rotation matrix. This means that they can transform the basis of the space to any other frame
Cartesian coordinate system
A Cartesian coordinate system specifies each point uniquely in a plane by a pair of numerical coordinates, which are the signed distances from the point to two fixed perpendicular directed lines, measured in the same unit of length...
in the space.
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
Euler angles
The Euler angles are three angles introduced by Leonhard Euler to describe the orientation of a rigid body. To describe such an orientation in 3-dimensional Euclidean space three parameters are required...
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 convention z-x-y (convention in which the line of nodes is perpendicular to z and Y axes, also named Y-X’-Z’’).For the same reason, any rotation matrix in 3D can be decomposed in a product of three of these rotations
Rotation operator (vector space)
This article derives the main properties of rotations in 3-dimensional space.The three Euler rotations are one way to bring a rigid object to any desired orientation by sequentially making rotations about axis' fixed relative to the object. However, this can also be achieved with one single...
.
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 rotationsActive and passive transformation
In the physical sciences, an active transformation is one which actually changes the physical position of a system, and makes sense even in the absence of a coordinate system whereas a passive transformation is a change in the coordinate description of the physical system . The distinction between...
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.
| xzx |  |
xzy |  |
|---|---|---|---|
| xyx |  |
xyz |  |
| yxy |  |
yxz |  |
| yxy |  |
yzx |  |
| zyz |  |
zyx |  |
| zxz |  |
zxy |  |