# Givens rotation

Let $A$ be an $m\times n$ matrix with $m\geq n$ and full rank (viz. rank $n$). An orthogonal matrix triangularization (QR Decomposition) consists of determining an $m\times m$ orthogonal matrix $Q$ such that

 $Q^{T}A=\begin{bmatrix}R\\ 0\end{bmatrix}$

with the $n\times n$ upper triangular matrix $R$. One only has then to solve the triangular system $Rx=Py$, where $P$ consists of the first $n$ rows of $Q$.

Householder transformations clear whole columns except for the first element of a vector. If one wants to clear parts of a matrix one element at a time, one can use Givens rotation, which is particularly practical for parallel implementation .

A matrix

 $G=\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}$

with properly chosen $c=\cos(\varphi)$ and $s=\sin(\varphi)$ for some rotation angle $\varphi$ can be used to zero the element $a_{ki}$. The elements can be zeroed column by column from the bottom up in the following order:

 $(m,1),(m,-1,1),\ldots,(2,1),(m,2),\ldots,\\ (3,2),\ldots,(m,n),\ldots,(n+1,n).$

$Q$ is then the product of $g=\frac{\left(2m-n-1\right)n}{2}$ Givens matrices $Q=G_{1}G_{2}\cdots G_{g}$.

To annihilate the bottom element of a $2\times 1$ vector:

 $\begin{pmatrix}c&s\\ -s&c\end{pmatrix}^{T}\begin{pmatrix}a\\ b\end{pmatrix}=\begin{pmatrix}r\\ 0\end{pmatrix}$

the conditions $sa+cb=0$ and $c^{2}+s^{2}=1$ give:

 $c=\frac{a}{\sqrt{a^{2}+b^{2}}},s=\frac{b}{\sqrt{a^{2}+b^{2}}}$

For “Fast Givens”, see [Golub89].

References

• Originally from The Data Analysis Briefbook (http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html)

• Golub89

Gene H. Golub and Charles F. van Loan: Matrix Computations, 2nd edn., The John Hopkins University Press, 1989.

Title Givens rotation GivensRotation 2013-03-22 12:06:10 2013-03-22 12:06:10 akrowne (2) akrowne (2) 8 akrowne (2) Algorithm msc 15A57 msc 65F25 GramSchmidtOrthogonalization