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.