next up previous contents index
Next: Conclusions Up: Implementation of the algorithm Previous: Numerical experiments   Contents   Index


Numerical experiments: Deflation possibilities

In the following experiment we want to illustrate the interplay between the Lanczos convergence behavior and the nested subspace iteration of the new method. We want to focus attention on the deflation possibilities of the new algorithm.

Let us construct a symmetric matrix having the eigenvalues as shown in Figure 6.6.

Figure 6.6: Eigenvalues of the symmetric matrix: 3 clusters
% latex2html id marker 35477
\includegraphics[scale=0.65]{figs/exp02}

There are three clusters of eigenvalues where the relative gap between the first and second cluster is equal to $ 0.5$ and the same as the relative gap between the second and third cluster. The first cluster has 20 eigenvalues geometrically distributed between $ 1$ and $ 10^{-2}$, the second cluster 20 eigenvalues between $ 5\cdot 10^{-3}$ and $ 5\cdot 10^{-5}$ and the third 60 eigenvalues between $ 2.5\cdot 10^{-5}$ and $ 2.5\cdot 10^{-7}$.

Let us first look at Figure 6.7 showing the behavior of the Ritz values for this example.

Figure 6.7: Behavior of the Ritz values
% latex2html id marker 35495
\includegraphics[scale=0.65]{figs/exp01}

Note that the same behavior is also obtained when using the classical tridiagonalization approach. However, the tridiagonal matrix obtained using this approach does not give a clear indication of the possible clusters or of deflation possibilities, i.e., no subdiagonal element becomes very small in magnitude. One might however chose a different initial transformation $ Q_0$ (see Chapter 5, Section 5.1) to increase the Lanczos convergence behavior towards the last cluster, but one will not be able to recognize two clusters in the tridiagonal matrix. The magnitude of the subdiagonal elements is plotted in Figure 6.8.

Figure 6.8: Magnitude of subdiagonal elements of similar tridiagonal matrix
% latex2html id marker 35501
\includegraphics[scale=0.65]{figs/exp03}

During the execution of the algorithm to obtain a similar semiseparable matrix, there will be a clear point where a diagonal block corresponding to the first cluster can be deflated and another point where a diagonal block corresponding to the second cluster can be deflated. Looking at Figure 6.7, we see that the eigenvalues of the first cluster are approximated well by the Lanczos-Ritz values from step 25 on. This means that at that moment the subspace iteration where the subspace has dimension $ 20$ will converge towards the subspace corresponding to the first cluster. The convergence factor will be $ 0.5$. This can clearly be seen in Figure 6.9. This figure shows for each step $ j=1,2,\ldots,n-1$ in the algorithm the norms of the subdiagonal blocks $ S(i:n,1:i-1)$ for $ i=n-j:n$. Each line in the plot indicates the change of the norm at each step of the algorithm. The line indicated by ``o'' corresponds to the norm of the subdiagonal block $ S(81:100,1:80)$.

Figure 6.9: Norms of subdiagonal matrices during the semiseparable reduction
% latex2html id marker 35517
\includegraphics[scale=0.65]{figs/exp04}

For the eigenvalues of the second cluster a similar convergence behavior occurs around step 45. The line indicated by ``*'' corresponds to the norm of the subdiagonal block $ S(61:100,1:60)$. The parallel lines in the figure having a smaller slope correspond to the subspace convergence behavior inside each of the clusters. Hence, at step $ 68$ a first diagonal $ 20 \times 20$ block can be deflated while at step $ 80$ the next diagonal $ 20 \times 20$ block can be deflated. This example shows clearly the influence of the convergence of the Lanczos-Ritz values on the convergence behavior of the nested subspace iteration.


next up previous contents index
Next: Conclusions Up: Implementation of the algorithm Previous: Numerical experiments   Contents   Index
Raf Vandebril 2004-05-03