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
Canonical name	GivensRotation
Date of creation	2013-03-22 12:06:10
Last modified on	2013-03-22 12:06:10
Owner	akrowne (2)
Last modified by	akrowne (2)
Numerical id	8
Author	akrowne (2)
Entry type	Algorithm
Classification	msc 15A57
Classification	msc 65F25
Related topic	GramSchmidtOrthogonalization