Construct modified Givens rotation

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

SROTMG/DROTMG

Name

SROTMG/DROTMG

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Construct modified Givens rotation

 

 

 

 

 

Purpose

The Givens rotation, G, that annihilates z1, if z1 ≠ 0 is

 

GW =

 

 

c

 

 

s

 

⋅

 

w1

 

 

…

wn

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

–s

 

 

c

 

 

z

1

 

 

…

z

n

 

 

 

 

 

 

 

 

where c = w

/r, s = z

/r, and r = ±(w

2+z 2)1/2. Computing G and applying it to

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

1

1

 

 

 

 

 

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

 

W = D

1 ⁄ 2

X =

 

 

 

d11 ⁄ 2

 

0

 

⋅

 

x1

 

 

… xn

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

d21 ⁄ 2

 

 

y1

 

 

… yn

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

These subprograms construct

 

1 ,

 

2 , and H such that GW is obtained in the

 

d

d

 

same factored form in which W was given

 

 

 

 

 

11 ⁄ 2

0

 

 

h11

 

 

 

h12

 

x1

… xn

 

 

 

GW =

 

d

 

⋅

 

 

 

⋅

 

 

 

 

 

 

 

 

 

 

 

21 ⁄ 2

 

h21

 

 

 

h22

y1

… yn

 

 

 

 

 

0

 

 

 

d

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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, d1 and d2 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-nmatrix to upper-triangular form via modified Givens rotations

requires O(n) square roots compared to the O(n2) required by ordinary Givens rotations. Refer to “Example 2” in the description of SROTM and DROTM.

Chapter 2 Basic Vector Operations 127