An orthogonal reduction to upper triangular semiseparable form

In this section only the reduction toards an upper triangular semiseparable form is described. All the other algorithms (as described in Theorem 52) can be deduced in an analogous way. Again we give some explicit formulas of the matrices. Based on these formulas the reader should be able to construct the algorithm.

Suppose we are at step $k$ of the algorithm, and we want to reduce an $m \times n$ matrix $A$ into upper triangular semiseparable form. (Note that for this implementation we start at the top of the matrix, while the reduction in the previous section started at the end.) This means that our matrix has a part of dimension $k\times n$ already of upper triangular semiseparable form, while a $j=n-k$ dimensional part is still not reduced. At the beginning of this step our matrix $A^{(k)}$ has the following form:

$$\left( \begin{array}{cccc\vert cc} d... ...j \\ \vdots & & & \vdots & \\ 0&\dots & & 0 & S_j^T & A_k \end{array} \right)$$ (6.5)

The matrix is partitioned in such a way that the upper left block is of dimension $(k-1)\times(k-1)$ and the lower right block is of dimension $(m-k+1) \times (n-k+1)$. The row vectors $S_j$ and $R_j$ are of length $(m-k)$ and $(n-k)$ respectively. The elements $d_i,c_i,s_i$ are defined in the same way as in the previous section. Equation (6.5) shows that the matrix $A^{(k)}$ has already the upper triangular part of the correct semiseparable form. In this step one wants to add one more row to the semiseparable structure, such that in the beginning of step $(k+1)$ we have a $(k+1)\times (k+1)$ upper triangular semiseparable matrix in the upper left $(k+1)\times (k+1)$ block. The first step consists of applying a Householder transformation or a sequence of Givens transformations to annihilate all the elements of the vector $R_j$ except for the first one. We choose to annihilate the elements with a Householder transformation $H^{(k)}_r$ (The $r$ denotes that we perform this transformation on the right of the matrix):

$$R_j H_r^{(k)} =\left( \alpha_j,0,\ldots,0 \right)=\hat{R}_j.$$

Applying this transformation onto the matrix $A^{(k)}$ we get:

$$\left( \begin{array}{cccc\vert cc} d... ...s & & & \vdots & \\ 0&\dots & & 0 & S_j^T & A_k H^{(k)}_r \end{array} \right).$$

At this stage we are ready to annihilate the element $\alpha_j$ by applying a Givens transformation such that

$$\left( d_{j+1},\alpha_{j} \right)G^{(k)}_{r,j} = \left( \alpha_{j+1},0 \right).$$

(Again the $r$ denotes that the Givens transformation is performed on the right-side of the matrix.) Note that the same result can be achieved when applying a Householder transformation $\tilde{H}^{(k)}_r$ such that

$$\left( d_{j+1},R_j \right)\tilde{H}^{(k)}_r=\left( \tilde{\alpha}_{j+1},0,\ldots,0 \right),$$

with $\vert\tilde{\alpha}_{j+1}\vert=\vert\alpha_{j+1}\vert$. After applying the Givens transformation $G^{(k)}_{r,j}$, our matrix has the following structure:

$$\left( \begin{array}{cccc\vert cc} d... ...& & & \vdots & \\ 0&\dots & & 0 & \hat{S}_j^T & \hat{A}_k \end{array} \right).$$ (6.6)

The vector $S_j$ and the matrix $A_k H^{(k)}_r$ also did change after applying the Givens transformation. The new vector and matrix are denoted as $\hat{S}_j$ and $\hat{A}_k$. The next step consists of applying another Householder transformation on the left of the matrix (6.6) such that:

$$H^{(k)}_l S_j^T = \left( \beta_{j+1},0,\ldots,0 \right)^T.$$

(The $l$ denotes that the transformation will be performed on the left side of the matrix.) Applying this transformation on the matrix and rewriting $H^{(k)}_l \hat{A}_k$ as

$$H^{(k)}_l \hat{A}^{(j)} = \left( \begin{array}{cc} d_{j} & R_{j-1}\\ S_{j-1} & A_{k-1} \end{array} \right)$$

gives us

$$\left( \begin{array}{cccc\vert ccc} ... ...} \\ [0.2cm] 0 &\hdots & & 0 & 0 & S_{j-1}^T & A_{k-1}\\ \end{array} \right).$$ (6.7)

In the next step we will add one row to the semiseparable structure. Apply the Givens transformation $G^{(k)}_{l,j}$:

$$G^{(k)}_{l,j}= \left( \begin{array}{cc} c_{j} & s_j \\ -s_j & c_j \end{array} \right)$$

on the rows $k$ and $k+1$ such that $G^{(k)}_{l,j} \left( c_{j+1}\alpha_{j+1},\beta_{j+1} \right)=\left( \tilde{d}_{j+1},0 \right)^T$. This will give us the following matrix:

$$\left( \begin{array}{cccc\vert ccc} ... ... & & \vdots \\ 0 &\hdots& &0& 0& S_{j-1}^T & A^{(j-1)} \\ \end{array} \right)$$

Applying now the Givens transformation $G^{(k)}_{r,j+1}$ to the columns $k$ and $k+1$, in order to annihilate the upper part of column $k$, we get a matrix which is essentially the same as the matrix (6.7). One can continue and chase the complete structure upwards.