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
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
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 MSC: 65F25 (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)