PlanetMath (more info)
 Math for the people, by the people.
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

$\displaystyle 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

$\displaystyle G = \begin{bmatrix} 1 & \cdots & 0 & \cdots & 0 & \cdots & 0 \ ... ...s & \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:

$\displaystyle (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:

$\displaystyle \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:

$\displaystyle 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)

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 13929 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)