- Givens rotation
In
numerical linear algebra , a Givens rotation is arotation in the plane spanned by two coordinates axes. Givens rotations are named afterWallace Givens who introduced them to numerical analysts in the 1950s while he was working atArgonne National Laboratory .Matrix representation
A Givens rotation is represented by a matrix of the form
:
where "c" = cos("θ") and "s" = sin("θ") appear at the intersections "i"th and "k"th rows and columns. That is, a Givens rotation matrix is the identity matrix with these substitutions::
The product "G"("i","k",θ)Tx represents a counterclockwise rotationof the vector x in the ("i","k") plane of θ radians, hence the name Givens rotation.
The main use of Givens rotations in
numerical linear algebra is to introduce zeros in vectors or matrices.This effect can, for example, be employed for computing theQR decomposition of a matrix. One advantage overHouseholder transformation s is that they can easily be parallelised, and another is that often for very sparse matrices they have a lower operation count.Stable calculation
When a Givens rotation matrix, "G"("i","k",θ), is multiplied times another matrix, "A", from the left, "GA", only rows "i" and "k" of "A" are affected. Thus we restrict attention to the following problem. Given "a" and "b", find "c" = cos θ and "s" = sin θ such that:Explicit calculation of θ is rarely necessary or desirable. Instead we directly seek "c", "s", and "r". An obvious solution would be:However, to avoid overflow and underflow, we use a different computation, employing the ratio "b"/"a" (which is tan θ) or its reciprocal (Golub & Van Loan 1996). And as Edward Anderson (2000) discovered in improving
LAPACK , a previously overlooked numerical consideration is continuity. To achieve this, we required "r" to be positive.if (b = 0) then {c ← copysign(1,a); s ← 0; r ← abs(a)} else if (a = 0) then {c ← 0; s ← copysign(1,b); r ← abs(b)} else if (abs(b) > abs(a)) then t ← a/b u ← copysign(sqrt(1+t*t),b) s ← 1/u c ← s*t r ← b*u else t ← b/a u ← copysign(sqrt(1+t*t),a) c ← 1/u s ← c*t r ← a*u
This is written in terms of the
IEEE 754r copysign(x,y) function, which provides a safe and cheap way to copy the sign of y to x. If that is not available, x*sgn(y), using thesign function , is an alternative.See also
*
Jacobi rotation References
* cite book
last = Golub
first = Gene H.
authorlink = Gene H. Golub
coauthors =Charles F. Van Loan
title = Matrix Computations
edition = 3/e
publisher = John Hopkins University Press
date = 1996
location = Baltimore
id = ISBN 978-0-8018-5414-9
* Anderson, Edward. (2000) " [http://www.netlib.org/lapack/lawns/downloads/ Discontinuous Plane Rotations and the Symmetric Eigenvalue Problem] ". LAPACK Working Note 150, University of Tennessee, UT-CS-00-454, December 4, 2000.
* D. Bindel, J. Demmel, W. Kahan, O. Marques. (2001) " [http://www.netlib.org/lapack/lawns/downloads/ On Computing Givens rotations reliably and efficiently] ". LAPACK Working Note 148, University of Tennessee, UT-CS-00-449, January 31, 2001.
Wikimedia Foundation. 2010.
