Givens rotation

Let $A$ be an $m\times n$ matrix with $m\ge 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=\left[\begin{array}{c}\hfill R\hfill \\ \hfill 0\hfill \end{array}\right]$$

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

with properly chosen $c=\cos (\phi )$ and $s=\sin (\phi )$ for some rotation angle $\phi$ 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),\mathrm{\dots },(2,1),(m,2),\mathrm{\dots },(3,2),\mathrm{\dots },(m,n),\mathrm{\dots },(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\mathrm{\cdots }{G}_g$.

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

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)

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