PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: High
Givens rotation (Algorithm)

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 = \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_1G_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

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




"Givens rotation" is owned by akrowne.
(view preamble | get metadata)

View style:

See Also: Gram-Schmidt orthogonalization

Log in to rate this entry.
(view current ratings)

Cross-references: product, order, angle, rotation, parallel, vector, columns, clear, Householder transformations, rows, upper triangular matrix, QR decomposition, orthogonal matrix, viz, rank, matrix
There are 2 references to this entry.

This is version 4 of Givens rotation, born on 2002-01-04, modified 2007-04-21.
Object id is 1215, canonical name is GivensRotation.
Accessed 16913 times total.

Classification:
AMS MSC65F25 (Numerical analysis :: Numerical linear algebra :: Orthogonalization)
 15A57 (Linear and multilinear algebra; matrix theory :: Other types of matrices )

Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)