HP MLIB User's Guide Vol. 1 7th Ed.

Chapter 2 Basic Vector Operations 127
Construct modified Givens rotation SROTMG/DROTMG
Name SROTMG/DROTMG
Construct modified Givens rotation
Purpose The Givens rotation, G, that annihilates z
1
, if z
1
≠ 0 is
where c = w
1
/r, s = z
1
/r, and r = ±(w
1
2
+z
1
2
)
1/2
. Computing G and applying it to
a pair of n vectors requires ∼4n floating-point multiplications, ∼2n
floating-point additions, and one square root.
The modified Givens rotation is a device for reducing this operation count.
Suppose that W above is available in factored form
These subprograms construct , , and H such that GW is obtained in the
same factored form in which W was given
H is chosen to have the same numerical stability as the standard Givens
rotation but better computational efficiency. Thus, H usually has two elements
equal to ±1. When this is true, computing H and applying it to a pair of
n-vectors requires ∼2n floating-point multiplications, ∼2n floating-point
additions, and no square roots. Companion VECLIB subprograms SROTM and
DROTM are provided to apply the modified Givens notation to a pair of vectors.
In most applications, d
1
and d
2
are initially set to 1, manipulated by SROTMG
or DROTMG as the modified Givens rotations are constructed, then applied to
the vectors as the final step in the computation. For example, the reduction of
an n-by-n matrix to upper-triangular form via modified Givens rotations
requires O(n) square roots compared to the O(n
2
) required by ordinary Givens
rotations. Refer to “Example 2” in the description of SROTM and DROTM.
GW
cs
s– c
w
1
… w
n
z
1
… z
n
⋅=
WD
12⁄
X
d
1
12⁄
0
0 d
2
12⁄
x
1
… x
n
y
1
… y
n
⋅==
d
1
d
2
GW
d
1
12⁄
0
0 d
2
12⁄
h
11
h
12
h
21
h
22
x
1
… x
n
y
1
… y
n
⋅⋅=