
144
G.H. Golub et al.
we thus need
2Kn 3
flops for the construction of the triangular Ti and 2n 3 for the outer
transformations
Q K and Qo.
Essentially this is 2n 3 flops per updated matrix.
If we now have some of the si = -1 we can not use Householder transformations anymore.
Indeed in order to construct the rows of A when needed, the matrices A~ "1 have to be
trangularized first, say with a QR factorization. The
Q R
factorization is performed in
an initial step. From there on the same procedure is followed, but using Givens rotations
instead of Householder transformations9 The