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:

    “If it is to be done well, child-rearing requires, more than most activities of life, a good deal of decentering from one’s own needs and perspectives. Such decentering is relatively easy when a society is stable and when there is an extended, supportive structure that the parent can depend upon.”
    —David Elkind (20th century)

    “Common sense is the measure of the possible; it is composed of experience and prevision; it is calculation appled to life.”
    —Henri-Frédéric Amiel (1821–1881)