Givens rotation

A Givens rotation acting on a matrix from the left is a row operation, moving data between rows but always within the same column. Unlike the elementary operation of row-addition, a Givens rotation changes both of the rows addressed by it. To understand how it is a rotation, one may denote the elements of one target row by x_1 through x_n and the elements of the other target row by y_1 through y_n: \begin{bmatrix} \vdots & \vdots & \ddots & \vdots \\ x_1 & x_2 & \dots & x_n \\ \vdots & \vdots & \ddots & \vdots \\ y_1 & y_2 & \dots & y_n \\ \vdots & \vdots & \ddots & \vdots \end{bmatrix} Then the effect of a Givens rotation is to rotate each subvector (x_k,y_k) by the same angle. As with row-addition, algorithms often choose this angle so that one specific element becomes zero, and whatever happens in remaining columns is considered acceptable side-effects. A Givens rotation acting on a matrix from the right is instead a column operation, moving data between two columns but always within the same row. As with action from the left, it rotates each subvector (x_k,y_k) by the same angle, but here these named elements occur in the matrix as \begin{bmatrix} \dots & x_1 & \dots & y_1 & \dots \\ \dots & x_2 & \dots & y_2 & \dots \\ \ddots & \vdots & \ddots & \vdots & \ddots \\ \dots & x_n & \dots & y_n & \dots \end{bmatrix} Some algorithms, especially those concerned with preserving matrix similarity, apply Givens rotations as a conjugate action: both rotating by one angle between two rows, and rotating by the same angle between the corresponding columns. In this case the effect on the four elements affected by both rotations is more complicated; a Jacobi rotation is such a conjugate action to the end of zeroing the two off-diagonal elements among these four. 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. == 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 and appear at the intersections th and th rows and columns. That is, for fixed , the non-zero elements of Givens matrix are given by: :\begin{align} g_{kk} &{}= 1 \qquad \text{for} \ k \ne i,\,j\\ g_{kk} &{}= c \qquad \text{for} \ k = i,\,j\\ g_{ji} &{} = -g_{ij}= -s\\ \end{align} The product represents a counterclockwise rotation of the vector in the plane of radians, hence the name Givens rotation. == Stable calculation ==

When a Givens rotation matrix, , multiplies another matrix, , from the left, , only rows and of are affected. Thus we restrict attention to the following counterclockwise problem. Given and , find and such that : \begin{bmatrix} c & -s \\ s & c \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} r \\ 0 \end{bmatrix} , where r = \sqrt{a^2 + b^2} is the length of the vector (a,b). Explicit calculation of is rarely necessary or desirable. Instead we directly seek and . An obvious solution would be :\begin{align} c &{}\larr a / r \\ s &{}\larr -b / r. \end{align} However, the computation for may overflow or underflow. An alternative formulation avoiding this problem 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. subroutine givens_rotation(a, b, c, s, r) real a, b, c, s, r real h, d if (b .ne. 0.0) then h = hypot(a, b) d = 1.0 / h c = abs(a) * d s = sign(d, a) * b r = sign(1.0, a) * h else c = 1.0 s = 0.0 r = a end if return end Furthermore, as Edward Anderson discovered in improving LAPACK, a previously overlooked numerical consideration is continuity. To achieve this, we require to be positive. The following MATLAB/GNU Octave code illustrates the algorithm. function [c, s, r] = givens_rotation(a, b) if b == 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); elseif a == 0; c = 0; s = -sign(b); r = abs(b); elseif abs(a) > abs(b); t = b / a; u = sign(a) * sqrt(1 + t * t); c = 1 / u; s = -c * t; r = a * u; else t = a / b; u = sign(b) * sqrt(1 + t * t); s = -1 / u; c = t / u; r = b * u; end end The IEEE 754 copysign(x,y) function, provides a safe and cheap way to copy the sign of y to x. If that is not available, , using the abs and sgn functions, is an alternative as done above. == Triangularization ==

Given the following Matrix: : A_1 = \begin{bmatrix} 6 & 5 & 0 \\ 5 & 1 & 4 \\ 0 & 4 & 3 \\ \end{bmatrix}, 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 and is required; element is zeroed first, using a rotation matrix of: :G_{1} = \begin{bmatrix} c & -s & 0 \\ s & c & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}. The following matrix multiplication results: : \begin{align} G_1 A_1 &{}= A_2 \\ &{} = \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}, \end{align} where :\begin{align} r &{}= \sqrt{6^2 + 5^2} \approx 7.8102 \\ c &{}= 6 / r \approx 0.7682 \\ s &{}= -5 / r \approx -0.6402. \end{align} Using these values for and and performing the matrix multiplication above yields : :A_2 \approx \begin{bmatrix} 7.8102 & 4.4813 & 2.5607 \\ 0 & -2.4327 & 3.0729 \\ 0 & 4 & 3 \\ \end{bmatrix} Zeroing element finishes off the process. Using the same idea as before, the rotation matrix is: :G_{2} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & c & -s \\ 0 & s & c \\ \end{bmatrix} Afterwards, the following matrix multiplication is: : \begin{align} G_2 A_2 &{}= A_3 \\ &{}\approx \begin{bmatrix} 1 & 0 & 0 \\ 0 & c & -s \\ 0 & s & c \\ \end{bmatrix} \begin{bmatrix} 7.8102 & 4.4813 & 2.5607 \\ 0 & -2.4327 & 3.0729 \\ 0 & 4 & 3 \\ \end{bmatrix}, \end{align} where :\begin{align} r &{}\approx \sqrt{(-2.4327)^2 + 4^2} \approx 4.6817 \\ c &{}\approx -2.4327 / r \approx -0.5196 \\ s &{}\approx -4 / r \approx -0.8544. \end{align} Using these values for and and performing the multiplications results in : :A_3 \approx \begin{bmatrix} 7.8102 & 4.4813 & 2.5607 \\ 0 & 4.6817 & 0.9665 \\ 0 & 0 & -4.1843 \\ \end{bmatrix}. This new matrix is the upper triangular matrix needed to perform an iteration of the QR decomposition. is now formed using the transpose of the rotation matrices in the following manner: :Q = G_{1}^T\, G_{2}^T. Performing this matrix multiplication yields: :Q \approx \begin{bmatrix} 0.7682 & 0.3327 & 0.5470 \\ 0.6402 & -0.3992 & -0.6564 \\ 0 & 0.8544 & -0.5196 \\ \end{bmatrix}. This completes two iterations of the Givens Rotation and calculating the QR decomposition can now be done. QR iteration variant If performing the above calculations as a step in the QR algorithm for finding the eigenvalues of a matrix, then one next wants to compute the matrix RQ , but one should not do so by first multiplying G_{1}^T and G_{2}^T to form Q , instead rather by multiplying each G_k^T by R G_1^T \dots G_{k-1}^T (on the right). The reason for this is that each multiplication by a Givens matrix on the right changes only two columns of R , thus requiring a mere O(n) arithmetic operations, which for n-1 Givens rotations sums up to O(n^2) arithmetic operations; multiplying by the general n \times n matrix Q would require O(n^3) arithmetic operations. Likewise, storing the full Q matrix amounts to n^2 elements, but each Givens matrix is fully specified the pairs (c,s) and (i,j), and n-1 of them can thus be stored in 4n-4 elements. In the example, \begin{aligned} R Q = A_3 (G_1^T G_2^T) ={}& (A_3 G_1^T) G_2^T \\ \approx{}& \begin{bmatrix} 8.8687& -1.5575& 2.5607\\ 2.9972& 3.5965& 0.9665\\ 0& 0& -4.1843 \end{bmatrix} G_2^T \approx \begin{bmatrix} 8.8687& 2.9972& 0.0\\ 2.9972&-1.0430&-3.5750\\ 0& -3.5750& 2.1742 \end{bmatrix} \end{aligned} ==Complex matrices==

A Givens rotation in the complex case would have to be a unitary matrix which maps a nonzero vector \begin{pmatrix} w \\ z \end{pmatrix} \in \mathbb{C}^2 to some \begin{pmatrix} r \\ 0 \end{pmatrix} . A straightforward solution for this is \frac{1}{ \sqrt{ |w|^2 + |z|^2 } } \begin{pmatrix} \overline{w} & \overline{z} \\ -z & w \end{pmatrix} which is even in SU(2) and makes r real = \sqrt{ |w|^2 + |z|^2 } . suggest the specialised form \begin{pmatrix} \cos(\theta) & -\sin(\theta) e^{i\phi} \\ \sin(\theta) e^{-i\phi} & \cos(\theta) \end{pmatrix} (coinciding with the above when w is real) for a Givens rotation. Their idea is to choose \theta and \phi so that e^{i\phi} = \frac{ \overline{z} }{ |z| } \bigg/ \frac{ \overline{w} }{ |w| } |w| \sin(\theta) + |z| \cos(\theta) = 0 and they explain how to obtain \cos(\theta),\sin(\theta),\cos(\phi),\sin(\phi) from three calls to a function for computing real Givens rotations. This more complicated initialisation can be justified by the observation that since half the matrix elements are real, fewer arithmetic operations are needed when applying this rotation. Note however that having only two real degrees of freedom means the r component of the result cannot in general be made real. A more elementary approach to the same end is to first multiply both rows being targeted by unit magnitude complex numbers of appropriate phase, so that both elements in the column considered become real – then a real Givens rotation suffices for zeroing out one of those entires. In the same notation as above, this amounts to \underbrace{ \frac{1}{ \sqrt{ |w|^2 + |z|^2 } } \begin{pmatrix} |w| & |z| \\ -|z| & |w| \end{pmatrix} }_G \underbrace{ \begin{pmatrix} \overline{w}/|w| & 0 \\ 0 & \overline{z}/|z| \end{pmatrix} }_D \begin{pmatrix} w \\ z \end{pmatrix} = \begin{pmatrix} \sqrt{ |w|^2 + |z|^2 } \\ 0 \end{pmatrix} where D is unitary (but in general not special unitary) because it is a diagonal matrix whose diagonal elements have unit magnitudes, and the product G D is unitary because a product of unitary matrices is unitary. Here we save some arithmetic operations because multiplication by D acts on each row separately, and multiplication by G has real coefficients throughout. A potential concern with the latter two methods is however that the choice of rotation is discontinuous along the w = 0 line, and for the last method also along the z = 0 line; even though the result of applying the rotation to \begin{pmatrix} w \\ z \end{pmatrix} varies continuously, the result of applying that same rotation to other columns of a matrix does not. For example, : the Golub–Van Loan method picks \begin{pmatrix} \frac{ \varepsilon }{\sqrt{ 1 + \varepsilon^2 }} & e^{i\alpha} \frac{ 1 }{\sqrt{ 1 + \varepsilon^2 }} \\ -e^{-i\alpha} \frac{ 1 }{\sqrt{ 1 + \varepsilon^2 }} & \frac{ \varepsilon }{\sqrt{ 1 + \varepsilon^2 }} \end{pmatrix} to rotate \begin{pmatrix} \varepsilon e^{i\alpha} & 10 \\ 1 & 0 \end{pmatrix} , producing \begin{pmatrix} e^{i\alpha}\sqrt{ 1 + \varepsilon^2 } & \frac{ 10\varepsilon }{\sqrt{ 1 + \varepsilon^2 }} \\ 0 & -10e^{-i\alpha} \frac{ 1 }{\sqrt{ 1 + \varepsilon^2 }} \end{pmatrix} . ==In Clifford algebras==

In Clifford algebras and its child structures such as geometric algebras, rotations are represented by bivectors. Givens rotations are represented by the exterior product of the basis vectors. Given any pair of basis vectors \mathbf e_i, \mathbf e_j Givens rotations bivectors are: : B_{ij} = \mathbf e_i \wedge \mathbf e_j. Their action on any vector is written: : v=e^{-(\theta/2)(\mathbf e_i \wedge \mathbf e_j)}u e^{(\theta/2)(\mathbf e_i \wedge \mathbf e_j)}, where : e^{(\theta/2)(\mathbf e_i \wedge \mathbf e_j)}= \cos(\theta/2)+ \sin(\theta/2) \mathbf e_i \wedge \mathbf e_j. ==Dimension 3==

There are three Givens rotations in dimension 3: : R_X(\theta) = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \cos \theta & -\sin \theta \\ 0 & \sin \theta & \cos \theta \end{bmatrix}. :\begin{align} \\ R_Y(\theta) = \begin{bmatrix} \cos \theta & 0 & -\sin \theta \\ 0 & 1 & 0 \\ \sin \theta & 0 & \cos \theta \end{bmatrix} \end{align} {{#tag:ref|The R_Y(\theta) rotation matrix immediately below is not a Givens rotation. The R_Y(\theta) 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 matrix below is actually the Givens rotation through an angle of -\theta. : R_Y(\theta) = \begin{bmatrix} \cos \theta & 0 & \sin \theta \\ 0 & 1 & 0 \\ -\sin \theta & 0 & \cos \theta \end{bmatrix} :\begin{align} \\ R_Z(\theta) = \begin{bmatrix} \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{bmatrix} \end{align} Given that they are endomorphisms they can be composed with each other as many times as desired, keeping in mind that . These three Givens rotations composed can generate any rotation matrix according to Davenport's chained rotation theorem. This means that they can transform the standard 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 R = R_Y(\theta_3)\cdot R_X(\theta_2)\cdot R_Z(\theta_1) transforms the basis of the space into a frame with angles roll, pitch and yaw YPR = (\theta_3,\theta_2,\theta_1) 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 rotation operators. The meaning of the composition of two Givens rotations is an operator that transforms vectors first by and then by , being and 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 means and means . 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. : == See also ==