Givens Rotation - Stable Calculation

Stable Calculation

When a Givens rotation matrix, G(i,j,θ), multiplies another matrix, A, from the left, GA, only rows i and j 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

\begin{align} r &{}\larr \sqrt{a^2 + b^2} \\ c &{}\larr a / r \\ s &{}\larr -b / r. \end{align}

However, the computation for r may overflow or underflow. An alternative formulation avoiding this problem (Golub & Van Loan 1996, §5.1.8) is implemented as the hypot function in many programming languages .

Furthermore, as Anderson (2000) discovered in improving LAPACK, a previously overlooked numerical consideration is continuity. To achieve this, we require 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 754 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 the sign function, is an alternative.

Read more about this topic:  Givens Rotation

Famous quotes containing the words stable and/or calculation:

    “In verity ... we are the poor. This humanity we would claim for ourselves is the legacy, not only of the Enlightenment, but of the thousands and thousands of European peasants and poor townspeople who came here bringing their humanity and their sufferings with them. It is the absence of a stable upper class that is responsible for much of the vulgarity of the American scene. Should we blush before the visitor for this deficiency?”
    —Mary McCarthy (1912–1989)

    ““To my thinking” boomed the Professor, begging the question as usual, “the greatest triumph of the human mind was the calculation of Neptune from the observed vagaries of the orbit of Uranus.”
    “And yours,” said the P.B.”
    —Samuel Beckett (1906–1989)