Question

Suppose we have a matrix A Rmxn. Recall the Golub-Kahan bidiagonalisation pro- cedure and the Lawson-Hanson-Chan (LHC) bidiagonalisation procedure (Section 8.2). Answer the following questions: (i) Workout the operation counts required by the Golub-Kahan bidiagonalisation (ii) Workout the operation counts required by the LHC bidiagonalisation. (iii) Using the ratio m, derive and explain under what circumstances the LHC is com- putationally more advantageous than the Golub-Kahan. we have a bidiagonal matrix B Rnxn, show that both B B and BB are tridiagonal matrices. Hint: recall that the operation counts of the QR factorisation (using Householder reflec- tion) is about 2mn2-In. You can relate those two bidiagonalisation procedures to the QR factorisation to work out their operation counts.

Answer 1

Answers:

(i) Consider

A=|x x x x

Householder reflectors applied alternatively from the left and the right will be used to zero parts of the matrix as follows:

INA=10 x x x
$\rightarrow U_{1}^{*}AV_{1} = \begin{bmatrix} x & x& 0& 0\\ 0 & x& x& x\\ 0 & x& x& x\\ 0 & x& x& x\\ 0 & x& x& x\\ \end{bmatrix}$

$U_{2}^{*}U_{1}^{*}A = \begin{bmatrix} x & x& x& x\\ 0 & x& x& x\\ 0 & 0& x& x\\ 0 & 0& x& x\\ 0 & 0& x& x\\ \end{bmatrix}$$\rightarrow U_{2}^{*}U_{1}^{*}A V_{1}V_{2}} = \begin{bmatrix} x & x& 0& 0\\ 0 & x& x& 0\\ 0 & 0& x& x\\ 0 & 0& x& x\\ 0 & 0& x& x\\ \end{bmatrix}$

0 0 0 r

00x10 01100 xx000 x0000 4

Note that no more right-multiplications were needed after the second step, so the corresponding identity matrices are omitted. The final matrix B is bi-diagonal. The procedure just illustrated is just like applying two separate QR factorizations applied to A and A∗

so the operation count is two times for QR Factorization

$2\left ( 2mn^{2} - \frac{2}{3}n^{3}\right ) = 4mn^{2} - \frac{4}{3}n^{3}$

(ii) The main idea for the Lawson-Hanson-Chan algorithm is to first compute a QR factorization of A, i.e., A = QR.

Then one applies the Golub-Kahan algorithm to R, i.e., R = UBV ∗ . Together this results in

A = QUBV ∗

This will produce operation costs

(iii) For

  Lawson Hanson and Chan is the better algorithm.

m 5 2

(iv) Let's take below matrix as bi-diagonal matrix

$B = \begin{bmatrix} x & x& 0& 0 \\ 0& x& x& 0\\ 0& 0& x& x\\ 0& 0& 0& x \end{bmatrix}$ and

r 0 0 0 BT=|x x 0 0 10 x x 0

The result is given by

$BB^{T} = \begin{bmatrix} 2x^{2} & x^{2}& 0& 0 \\ x^{2}& 2x^{2}& x^{2}& 0\\ 0& x^{2}& 2x^{2}& x^{2}\\ 0& 0& x^{2}& 2x^{2} \end{bmatrix}$