An orthogonal reduction of a matrix to upper (lower) triangular semiseparable form

Similar to the Householder bidiagonalization [90], the algorithm given here makes use of orthogonal transformations, i.e., Givens and Householder transformations, to reduce the matrix $A$ into an upper triangular semiseparable matrix. The algorithm can be retrieved from the constructive proof of the following theorem.

Theorem 51   Let $A\in \mathbb{R}^{m\times n},$ $m \geq n$. There exist two orthogonal matrices $U \in \mathbb{R}^{m \times m}$ and $V \in \mathbb{R}^{n \times n}$ such that

$$U^T A V = \left(\begin{array}{c} S_u\\ 0 \end{array}\right),$$

where $S_u$ is an upper triangular semiseparable matrix.

The case $n \geq m$ is formulated in Theorem 52.

Proof. The proof given here is a constructive one. We prove the existence of such a transformation by reducing the matrix $A$ to the appropriate form by using Givens and Householder transformations.

The proof is given by finite induction. The proof is outlined for a matrix $A\in \mathbb{R}^{m\times n},$ with $m=6$ and $n=5$, as this case illustrates the general case. The side on which the operations are performed plays a very important role. In fact, the first phase of the algorithm constructs two sequences of matrices $A^{(l)}$ and $A^{(l)}_{k,j}$, with $l=1,\ldots,n$, $k=0,\ldots,l+1$, and $j,=0,\ldots,l$, starting from $A^{(1)}=A$, according to one of the following rules:

$$U^{(l)}_{k+1} A^{(l)}_{k,j} = A^{(l)}_{k+1,j} ,\quad A^{(l)}_{k,j} V^{(l)}_{j+1} = A^{(l)}_{k,j+1} .$$

Furthermore, one lets $A^{(l)}_{0,0} =A^{(l)}$ and $A^{(l+1)}= A^{(l)}_{l+1,l}$. The applied transformations to the left and to the right of $A^{(l)}_{k,j}$ are Givens and/or Householder transformations.

Step 1.

In this first step of the algorithm three orthogonal matrices ${U^{(1)}_{1}}^T$, ${U^{(1)}_{2}}^T$ and $V^{(1)}_{1}$ are to be found, such that the matrix $A^{(2)}={U^{(1)}_{2}}^T{U^{(1)}_{1}}^TA^{(1)}V^{(1)}_{1}$, with $A^{(1)}=A$, has the following properties: the first two rows of the matrix $A^{(2)}$ satisfy already the semiseparable structure and the first column of $A^{(2)}$ is zero below the first element. A Householder transformation $V^{(1)}_{1}$ is applied to the right of $A^{(1)}= A^{(1)}_{0,0}$ in order to annihilate all the elements in the first row except for the first one. The elements denoted with $\otimes$ will be annihilated, and the ones denoted with $\boxtimes$ mark the part of the matrix having already a semiseparable structure:

$$\left( \begin{array}{ccccc} \times & \otimes & \otimes & \otimes ... ...& \times \\ \times & \times & \times & \times & \times \\ \end{array} \right) \underrightarrow{ A^{(1)}_{0,0} V^{(1)}_{1}} \left( \begin{array}{ccccc} \times & 0 & 0 & 0 & 0\\ \times & \t... ... \times \\ \otimes & \times & \times & \times & \times \\ \end{array} \right)$$

$$\Updownarrow$$

$$\begin{array}{r} \hphantom{A} \\ A^{(1)}_{0,0} = A^{(1)} \end{array} \underrightarrow{ A^{(1)}_{0,0} V^{(1)}_{1}} \begin{array}{l} \hphantom{A} \\ A^{(1)}_{0,1} . \end{array}$$

A Householder transformation ${U^{(1)}_{1}}^T$ is now applied to the left of $A^{(1)}_{0,1}$ in order to annihilate all the elements in the first column except the first two ones, $A^{(1)}_{1,1} ={U^{(1)}_{1}}^T A^{(1)}_{0,1} ,$ followed by a Givens transformation ${U^{(1)}_{2}}^T$ applied to the left of $A^{(1)}_{1,1}$ in order to annihilate the second element in the first column. As a consequence, the first two rows of $A^{(1)}_{2,1}$ have already a semiseparable structure:

$$\left( \begin{array}{ccccc} \times & 0 & 0 & 0 & 0 \\ \otimes & ... ...imes & \times \\ 0 & \times & \times & \times & \times \\ \end{array} \right) \underrightarrow{{U^{(1)}_{2}}^T A^{(1)}_{1,1} } \left( \begin{array}{ccccc} \boxtimes & \boxtimes & \boxtimes & \... ...imes & \times \\ 0 & \times & \times & \times & \times \\ \end{array} \right)$$

$$\Updownarrow$$

$$\begin{array}{r} \hphantom{A} \\ A^{(1)}_{1,1} \end{array} \underrightarrow{{U^{(1)}_{2}}^T A^{(1)}_{1,1} } \begin{array}{l} \hphantom{A} \\ A^{(1)}_{2,1} . \end{array}$$

Then we put $A^{(2)}= A^{(1)}_{2,1}$.

Step $k$

By induction, for $k>1$. The first $k$ rows of $A^{(k)}$ have a semiseparable structure and the first $k-1$ columns are already in an upper triangular form. In fact, the upper left $k$ by $k$ block is already an upper triangular semiseparable matrix. Without loss of generality, let us assume $k =3$. This means that $A^{(3)}$ has the following structure:

$$A^{(3)}= \left( \begin{array}{ccccc}... ...& \times & \times \\ 0 & 0 & \times & \times & \times \\ \end{array} \right).$$

The aim of this step is to make the upper triangular semiseparable structure in the first $4$ rows and the first $3$ columns of the matrix. To this end, a Householder transformation $V^{(3)}_{1}$ is applied to the right of $A^{(3)}$, chosen in order to annihilate the last two elements of the first row of $A^{(3)}$. Note that because of the dependency between the first three rows, $V^{(3)}_{1}$ annihilates the last two entries of the second and third row, too. Furthermore, a Householder transformation is performed to the left of the matrix $A^{(3)}_{0,1}$ to annihilate the last two elements in column $3$:

$$\left( \begin{array}{ccccc} \boxtimes & \boxtimes & \boxtimes & 0... ...& \times & \times \\ 0 & 0 & \otimes & \times & \times \\ \end{array} \right) \underrightarrow{{U^{(3)}_{1}}^T A^{(3)}_{0,1} } \left( \begin{array}{ccccc} \boxtimes & \boxtimes & \boxtimes & 0... ...0 & 0 & \times & \times \\ 0 & 0 & 0 & \times & \times \\ \end{array} \right)$$

$$\Updownarrow$$

$$\begin{array}{r} \hphantom{A} \\ A^{(3)}_{0,1} = A^{(3)}_{0,0} V^{(3)}_{1} \end{array} \underrightarrow{{U^{(3)}_{1}}^T A^{(3)}_{0,1} } \begin{array}{l} \hphantom{A} \\ A^{(3)}_{1,1} . \end{array}$$

The Givens transformation ${U^{(3)}_{2}}^T$ is now applied to the left of the matrix $A^{(3)}_{1,1} ,$ annihilating the element marked with a circle:

$$\left( \begin{array}{ccccc} \times & \boxtimes & \boxtimes & 0 & ... ...0 & 0 & \times & \times \\ 0 & 0 & 0 & \times & \times \\ \end{array} \right) \underrightarrow{{U^{(3)}_{2}}^T A^{(3)}_{1,1} } \left( \begin{array}{ccccc} \times & \boxtimes & \boxtimes & 0 & ... ...0 & 0 & \times & \times \\ 0 & 0 & 0 & \times & \times \\ \end{array} \right)$$

$$\Updownarrow$$

$$\begin{array}{r} \hphantom{A} \\ A^{(3)}_{1,1} \end{array} \underrightarrow{{U^{(3)}_{2}}^T A^{(3)}_{1,1} } \begin{array}{l} \hphantom{A} \\ A^{(3)}_{2,1} . \end{array}$$

Dependency is now created between the fourth and the third row. Nevertheless, as it can be seen in the figure above, the upper part does not satisfy the semiseparable structure, yet. A chasing technique is used in order to chase the nonsemiseparable structure upwards and away, by means of Givens transformations. Applying $V^{(3)}_{2}$ to the right to annihilate the entry $(2,3)$ of $A^{(3)}_{2,1}$, a nonzero element is introduced in the third row on the second column (i.e. in position $(3,2)$). Because of the semiseparable structure, this operation introduces two zeros in the third column, namely in the first and second row. Annihilating the element just created in the third row with a Givens transformation to the left, the semiseparable structure holds between the second and the third row:

$$\left( \begin{array}{ccccc} \times & \boxtimes & 0 & 0 & 0\\ 0 &... ...0 & 0 & \times & \times \\ 0 & 0 & 0 & \times & \times \\ \end{array} \right) \underrightarrow{{U^{(3)}_{3}}^T A^{(3)}_{2,2} } \left( \begin{array}{ccccc} \times & \boxtimes & 0 & 0 & 0\\ 0 &... ...0 & 0 & \times & \times \\ 0 & 0 & 0 & \times & \times \\ \end{array} \right)$$

$$\Updownarrow$$

$$\begin{array}{r} \hphantom{A} \\ A^{(3)}_{2,2} = A^{(3)}_{2,1} V^{(3)}_{2} \end{array} \underrightarrow{{U^{(3)}_{3}}^T A^{(3)}_{2,2} } \begin{array}{l} \hphantom{A} \\ A^{(3)}_{3,2} . \end{array}$$

This up-chasing of the semiseparable structure can be repeated to create a complete upper semiseparable part starting from row 4 to row 1.

$$\left( \begin{array}{ccccc} \times & 0 & 0 & 0 & 0\\ \otimes & \... ...0 & 0 & \times & \times \\ 0 & 0 & 0 & \times & \times \\ \end{array} \right) \underrightarrow{{U^{(3)}_{4}}^T A^{(3)}_{3,3} } \left( \begin{array}{ccccc} \boxtimes & \boxtimes & \boxtimes & \... ...0 & 0 & 0 & \times & \times \\ 0 & 0 & 0 & \times & \times \end{array} \right)$$

$$\Updownarrow$$

$$\begin{array}{r} \hphantom{A} \\ A^{(3)}_{3,3} = A^{(3)}_{3,2} V^{(3)}_{3} \end{array} \underrightarrow{{U^{(3)}_{4}}^T A^{(3)}_{3,3} } \begin{array}{l} \hphantom{A} \\ A^{(3)}_{4,3} . \end{array}$$

Then we put $A^{(4)}= A^{(3)}_{4,3}$. This proves the induction step.

Step $n+1$

This step is only performed if $m>n$. Finally, a Householder transformation has to be performed to the left to have a complete upper triangular semiseparable structure. In fact, suppose, the matrix has already the semiseparable structure in the first $n$ rows, then one single Householder transformation is needed to annihilate all the elements in the $n$th column below the $n$th row:

$$\left( \begin{array}{ccccc} \boxtimes & \boxtimes & \boxtimes & \... ... \\ 0 & 0 & 0 & 0 & \boxtimes \\ 0 & 0 & 0 & 0 & \times \\ \end{array} \right) \underrightarrow{{U^{(5)}_{1}}^T A^{(5)}_{0,0} } \left( \begin{array}{ccccc} \boxtimes & \boxtimes & \boxtimes & \... ...mes \\ 0 & 0 & 0 & 0 & \boxtimes \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right)$$

$$\Updownarrow$$

$$\begin{array}{r} \hphantom{A} \\ A^{(5)} \end{array} \underrightarrow{{U^{(5)}_{1}}^T A^{(5)}_{0,0} } \begin{array}{l} \hphantom{A} \\ A^{(5)}_{1,0} . \end{array}$$

After the latter Householder transformation, the desired upper triangular semiseparable structure is created and the theorem is proved.

$\qedsymbol$

The reduction just described is obtained by applying Givens and Householder transformations to $A$. Note that the computational complexity of applying the Householder transformations is the same as of the standard procedure that reduces matrices into bidiagonal form using Householder transformations. This complexity is $4 mn^2 -4/3 n^3$ (see [91]). At step $k$ of the reduction procedure, described above, $k$ Givens transformations $U^{(k)}_{j},j=2,3,\ldots,k+1$ are applied to the left and $k-1$ Givens transformations $V^{(k)}_{j}$, $j=2,3,\ldots,k$ are applied to the right of the almost upper triangular semiseparable part of $A^{(k)}_{1,1}$. The purpose of these Givens transformations is to chase the bulge on the subdiagonal upwards while maintaining the upper triangular semiseparable structure in the upper part of the matrix. Applying the $k-1$ Givens transformations $V^{(k)}_{j}$ on the first $(k+1)$ columns of $A^{(k)}_{1,1}$ requires only $O(k)$ flops using the Givens-vector representation of the upper left upper triangular semiseparable matrix. Applying the $k$ Givens transformations $U^{(k)}_{j}$ on the upper left part of the matrix $A^{(k)}_{1,1}$ requires also only $O(k)$ flops using the Givens-vector representation of the upper triangular semiseparable matrix. Because the upper right part of the matrix $A^{(k)}_{1,1}$ can be written as a $(k+1)\times(n-k-1)$ matrix of rank $1$, applying the Givens transformations $U^{(k)}_{j}$ on this part of $A^{(k)}_{1,1}$ also requires only $O(k)$ flops. Hence applying the Givens transformations during the whole reduction requires $O(n^2)$ flops.

A generalization of the previous result is formulated in the following theorem.

Theorem 52   Let $A\in \mathbb{R}^{m\times n}$. There exist two orthogonal matrices $U \in \mathbb{R}^{m \times m}$ and $V \in \mathbb{R}^{n \times n}$ such that

• for $m \geq n$:
  $$U^T A V = \left(\begin{array}{c} S_l\\ 0 \end{array}\right),$$
  where $S_l$ is a lower triangular semiseparable matrix,
• for $m \leq n$:
  $$U^T A V = \left(\begin{array}{cc} S_u& 0 \end{array}\right),$$
  where $S_u$ is an upper triangular semiseparable matrix,
• for $m \leq n$:
  $$U^T A V = \left(\begin{array}{cc} S_l& 0 \end{array}\right),$$
  where $S_l$ is a lower triangular semiseparable matrix.

Proof. Using the transpose operation and permuting rows or columns, these results can easily be obtained from Theorem 51. $\qedsymbol$