An efficient transformation from $\mathbf{v}$ to $\mathbf{e}_1$

The reduction of an arbitrary vector $\mathbf{v}$ to $\beta\mathbf{e}_1$, a multiple of the first basis vector can easily be accomplished by performing a Householder transformation or $n-1$ Givens transformations. Unfortunately applying the Householder or the Givens transformations, onto the Hessenberg-like matrix creates an overhead on distortion in the matrix $Z$, which cannot be removed efficiently. It seems that a more appropriate technique is needed to reduce the complexity of restoring the structure of the disturbed matrix $Z$.

Reconsidering the single shift case, we know that the Givens transformations needed for bringing the vector $\mathbf{v}$ back to $\beta\mathbf{e}_1$ are closely related to the Givens transformations used in the Givens-vector representation (see Section ). Hence, we will search how to link the transformation of $\mathbf{v}$ to $\beta\mathbf{e}_1$ with the Givens-vector representation of the matrix $Z$.

Assume we have the following matrix $\tilde{Z}$, whose first column we would like to reduce efficiently to $\beta\mathbf{e}_1$. Denote, $Z^{(1)}=Z$ and the $\sigma_i$ are suitably chosen shifts:

$$\tilde{Z}=\left(Z^{(1)}-\sigma_1 I\right)\left(Z^{(1)}-\sigma_2 I\right)\ldots \left(Z^{(1)}-\sigma_k I\right).$$

The matrix $Z^{(1)}$ is represented with the Givens-vector representation, and hence we have $Z^{(1)}=Q^{(1)}R^{(1)}$, in which the matrix $Q^{(1)}$ contains the Givens transformations, from the representation, and the matrix $R^{(1)}$ is an upper triangular matrix. This leads to:

$$\tilde{Z}=Q^{(1)}\left(R^{(1)}-H^{(1)}_1\right)Q^{(1)}\left(R^{(1)}-H^{(1)}_2\right)\ldots Q^{(1)}\left(R^{(1)}-H^{(1)}_k\right),$$

in which $H^{(1)}_i={Q^{(1)}}^H\sigma_i I$, for $i=1,\ldots,k$ and all matrices $H^{(1)}_i$ are Hessenberg matrices.

We will now transform the first column of the matrix $\tilde{Z}$ to $\beta\mathbf{e}_1$, but in such a way that we can perform these transformations efficiently, as similarity transformations onto the matrix $Z^{(1)}$.

Perform the transformation ${Q^{(1)}}^H$ onto the matrix $\tilde{Z}$

$${Q^{(1)}}^H \tilde{Z} = \left(R^{(1)}-H^{(1)}_1\right)Q^{(1)}\left(R^{(1)}-H^{(1)}_2\right)\ldots Q^{(1)}\left(R^{(1)}-H^{(1)}_k\right)$$

$$= \left(R^{(1)}Q^{(1)}-\sigma_1 I\right)\left(R^{(1)}Q^{(1)}-\sigma... ...dots \left(R^{(1)}Q^{(1)}-\sigma_{k-1} I\right) \left(R^{(1)}-H^{(1)}_k\right).$$

The matrix product $R^{(1)} Q^{(1)}$ produces a new Hessenberg-like matrix $Z^{(2)}$. (Check the correspondence with the right to left representation of Hessenberg-like matrices). The $RQ$-factorization of the matrix considered can easily be transformed to the $QR$-factorization. Due to the connection with the Givens-vector representation this can be done efficiently, moreover we will see further on in the text that we do need this transition anyway. Denote this as $Z^{(2)}=Q^{(2)}R^{(2)}$. Important to remark is the fact that the matrix $Z^{(2)}$ is in fact the result of performing a step of the $QR$-algorithm without shift onto the matrix $Z^{(1)}$, this is equivalent as in the single shift approach discussed in [28]. We have the equality $Z^{(2)}= {Q^{(1)}}^H Z^{(1)} Q^{(1)}$.

We obtain the following relations (with $H^{(2)}_i={Q^{(2)}}^H \sigma_i I$, for $i=1,\ldots,k-1$):

$${Q^{(1)}}^H \tilde{Z} = Q^{(2)}\left(R^{(2)}-H^{(2)}_1\right)Q^{(2)}\left(R^{(2)}-H^{(2)}... ...\ldots Q^{(2)}\left(R^{(2)}-H^{(2)}_{k-1}\right) \left(R^{(1)}-H^{(1)}_k\right)$$

$${Q^{(2)}}^H {Q^{(1)}}^H \tilde{Z} = \left(R^{(2)}Q^{(2)}-\sigma_1 I \right)\left(R^{(2)}Q^{(2)}-\sigm... ...-2} I\right) \left(R^{(2)}-H^{(2)}_{k-1}\right) \left(R^{(1)}-H^{(1)}_k\right).$$

It is clear that the procedure can easily be continued by defining

$$Z^{(3)}={Q^{(2)}}^H Z^{(2)} Q^{(2)} = R^{(2)} Q^{(2)},$$

which is the result of applying another step of $QR$-without shift onto the matrix $Z^{(2)}$.

As a result we obtain that, if for every $i=1,\ldots,k$

$$Z^{(i)} = Q^{(i)}R^{(i)},$$

$$Z^{(i+1)} = {Q^{(i)}}^H Z^{(i)} Q^{(i)}=R^{(i)} Q^{(i)},$$

$$H^{(i)}_{k-i+1} = {Q^{(i)}}^H \sigma_{k-i+1} I$$

the following relation holds

$${Q^{(k)}}^H \ldots {Q^{(1)}}^H \tilde{Z} = \left(R^{(k)}-H^{(k)}_1\right)\left(R^{(k-1)}- H^{(k-1)}_2\right)... ...{k-2}\right) \left(R^{(2)}-H^{(2)}_{k-1}\right) \left(R^{(1)}-H^{(1)}_k\right).$$ (4)

The first column of ${Q^{(k)}}^H \ldots {Q^{(1)}}^H \tilde{Z}$ has only the first $k+1$ elements different from zero as it is the product of $k$ Hessenberg matrices. These elements can be computed easily as the matrices $H^{(i)}_{k-i+1}={Q^{(i)}}^H \sigma_{k-i+1} I$, in which $Q^{(k)}$ is a sequence of Givens transformations from bottom to top. For computing the first column of the matrix product ${Q^{(k)}}^H \ldots {Q^{(1)}}^H \tilde{Z}$, we efficiently compute the multiplication of the right-hand side of Equation  with $\mathbf{e}_1$.

Moreover combining all these transformations, and perform them as a similarity transformation onto the matrix $Z^{(1)}$ gives us

$${Q^{(k)}}^H \ldots {Q^{(2)}}^H {Q^{(1)}}^H Z^{(1)} Q^{(1)} Q^{(2)}\ldots Q^{(k)}$$

$$= {Q^{(k)}}^H \ldots {Q^{(2)}}^H Z^{(2)} Q^{(2)}\ldots Q^{(k)}$$

$$= {Q^{(k)}}^H \ldots {Q^{(3)}}^H Z^{(3)} Q^{(3)}\ldots Q^{(k)}$$

$$= Z^{(k)}.$$

This corresponds to performing $k$ steps of the $QR$-method without shift onto the matrix $Z^{(1)}$, which can be performed efficiently in tex2html_wrap_inline$O(n^2)$. (Especially in the semiseparable case one can perform these steps in linear time tex2html_wrap_inline$O(n)$.)

To complete the reduction of $\mathbf{v}$ to $\beta\mathbf{e}_1$, we have to annihilate $k$ of the $k+1$ nonzero elements of the vector ${Q^{(k)}}^H \ldots {Q^{(1)}}^H \tilde{Z} \mathbf{e}_1$. This can be done by performing $k$ Givens transformations $\hat{G}_k\ldots \hat{G}_1$ annihilating first the nonzero element in position $k+1$, followed by annihilating the element in position $k$ and so forth. This results in the matrix

$$\hat{G}_k^H\ldots \hat{G}_1^H Z^{(k)} \hat{G}_1 \ldots \hat{G}_k,$$

which we have to bring back via similarity transformations to Hessenberg-like form.

Let us summarize this step. In order to start the implicit procedure, in case of $k$ shifts, we have to perform $k$ steps of $QR$-without shift onto the matrix $Z^{(1)}$. Moreover we have to use these unitary transformations to compute the first column ${Q^{(k)}}^H \ldots {Q^{(1)}}^H \tilde{Z} \mathbf{e}_1$ in an efficient way. The result of these $k$ $QR$-steps without shift onto $Z^{(1)}$ gives us again a Hessenberg-like matrix $Z^{(k)}$. The vector ${Q^{(k)}}^H \ldots {Q^{(1)}}^H \tilde{Z} \mathbf{e}_1$, is still not a multiple of $\mathbf{e}_1$ and hence an extra $k$ Givens transformations are needed to transform this vector to $\beta\mathbf{e}_1$.These final $k$ Givens transformations disturb significantly the Hessenberg-like structure of the matrix ${Z}^{(k)}$. As a result of a step of $QR$, we know that the matrix will again be of Hessenberg-like form. Hence we will develop in the next section a chasing technique for restoring the structure.