Givens rotation


Let A be an m×n matrix with mn and full rank (viz. rank n). An orthogonal matrixMathworldPlanetmath triangularization (QR DecompositionMathworldPlanetmath) consists of determining an m×m orthogonal matrix Q such that

QTA=[R0]

with the n×n upper triangular matrixMathworldPlanetmath 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=[10000cs00-sc00001]

with properly chosen c=cos(φ) and s=sin(φ) for some rotationMathworldPlanetmath angle φ can be used to zero the element aki. The elements can be zeroed column by column from the bottom up in the following order:

(m,1),(m,-1,1),,(2,1),(m,2),,(3,2),,(m,n),,(n+1,n).

Q is then the product of g=(2m-n-1)n2 Givens matrices Q=G1G2Gg.

To annihilate the bottom element of a 2×1 vector:

(cs-sc)T(ab)=(r0)

the conditions sa+cb=0 and c2+s2=1 give:

c=aa2+b2,s=ba2+b2

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 AlgorithmMathworldPlanetmath
Classification msc 15A57
Classification msc 65F25
Related topic GramSchmidtOrthogonalization