next up previous contents index
Next: Locking or Purging a Up: Implicitly Restarted Arnoldi Method Previous: Deflation and Stopping Rules   Contents   Index


Orthogonal Deflating Transformation

We shall utilize a special orthogonal transformation to implement these deflation schemes. The deflation schemes are related to an eigenvector associated with a Ritz value that is to be deflated (either locked or purged). Given a vector $y$ of unit length, Algorithm 7.8 computes an orthogonal matrix $Q$ such that $Q e_1 = y $ (hence $y = Q^* e_1 $). The following orthogonal deflating transformation Algorithm 7.8 is identical to Algorithm 4.9 used in IRLM (see §4.5), but for completeness, we present it again.


\begin{algorithm}{Orthogonal Deflating Transformation for IRAM
}
{
\begin{tabb...
... \tau_o = \tau$\\
{\rm (14)} \> \>{\bf end for}
\end{tabbing}}
\end{algorithm}

The orthogonal matrix $Q$ constructed as prescribed in Algorithm 7.8 has a very special form and may be written as Q = R + y e_1^*, with R e_1 = 0 , R^* y = 0, where $R$ is upper triangular. It may also be written as Q = L + y g^* , with L e_1 = 0 , L^* y = e_1 - g, where $L$ is lower triangular, and $g^* \equiv e_1^* + \frac{1}{\eta_1} e_1^* R $.

Now, consider the matrix $Q^* H Q$. The substitutions $ Q^* = (L + y g^* )^*$, $ Q = (R + y e_1^* )$ from (7.19) and (7.18) will give Q^* H Q &=& Q^* H ( R + y e_1^*)
&=& (L^* + g y^*) H R + Q^*Hy e_1^*
&=& L^*HR + g y^*H R + Q^*Hy e_1^*. Since both $L^*$ and $R$ are upper triangular, it follows that $L^*HR$ is upper Hessenberg, with the first row and the first column each being zero due to $Le_1 = Re_1 = 0$.

From this discussion, we see that when $y$ is a right eigenvector of $H$ with $Hy = y \theta$, then $H_+ \equiv Q^* H Q$ is of the form H_+ = [ cc & h^*
0 & H_2
].

On the other hand, when $y$ is a left eigenvector of $H$ with $y^*H = \theta y^*$, then $H_+ \equiv Q^* H Q$ is of the form H_+ = [ cc & 0
h & H_2
], where $H_2$ is upper Hessenberg.

We shall use (7.20) for locking a converged Ritz value, and we shall use (7.21) to purge an unwanted but converged Ritz value.

It should be noted that, as computed by Algorithm 7.8, $Q$ will have componentwise relative errors on the order of machine precision $\epsilon_M$ with no element growth. Moreover, extension to complex arithmetic is completely straightforward (unlike Givens or Householder transformations).



Subsections
next up previous contents index
Next: Locking or Purging a Up: Implicitly Restarted Arnoldi Method Previous: Deflation and Stopping Rules   Contents   Index
Susan Blackford 2000-11-20