Numerical experiments: Deflation possibilities

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

There are three clusters of eigenvalues where the relative gap between the first and second cluster is equal to and the same as the relative gap between the second and third cluster. The first cluster has 20 eigenvalues geometrically distributed between and , the second cluster 20 eigenvalues between and and the third 60 eigenvalues between and .Let us first look at Figure 6.7 showing the behavior of the Ritz values for this example.

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 (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. 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 will converge towards the subspace corresponding to the first cluster. The convergence factor will be . This can clearly be seen in Figure 6.9. This figure shows for each step in the algorithm the norms of the subdiagonal blocks for . 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 . 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 . The parallel lines in the figure having a smaller slope correspond to the subspace convergence behavior inside each of the clusters. Hence, at step a first diagonal block can be deflated while at step the next diagonal 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.