Numerical Experiments

In this section three numerical experiments are performed. In a first experiment the accuracy of the reduction algorithm is compared w.r.t. the orthogonal similarity reduction to tridiagonal and semiseparable form. In a second experiment the computational complexity of these three reduction algorithms is compared and in the final experiment the reduction algorithm is examined for special choices of the diagonal, in correspondence with the previously given theorems. All the experiments are performed in Matlab ⁶, and the software can be freely downloaded from the website:
http://www.cs.kuleuven.ac.be/$\sim$marc/software

For the first experiment a set of test matrices was generated of dimensions $2^i$ for $i=3,\ldots,11$. The symmetric matrices were constructed in such a way that they have as eigenvalues $[1:2^i]$ for each choice of $i$. In Figure 2 the relative accuracy of the eigenvalues of the reduced matrices w.r.t. the original matrices is given. Denote the original eigenvalues with $\lambda_i$ and the computed ones with $\tilde{\lambda}_i$, then the relative accuracy is calculated as

$$\frac{\max_{i} \vert \lambda_i-\tilde{\lambda}_i \vert }{ \max_{i} \vert \lambda_i \vert}$$

It can be seen clearly that all three approaches are equally accurate.

Figure 2: Relative residual of the eigenvalues.

In the second experiment the computational complexity of the three approaches was compared. The computational complexity of the reduction to tridiagonal and semiseparable form differs in an extra $9n^2$ operations that need to be performed to get the semiseparable structure. The reduction to diagonal-plus-semiseparable form needs an extra $\sum_{j=1}^n 2j = n(n-1)$ operations for the extra additions and substractions needed for making the matrix semiseparable with that specific diagonal. Figure 3 shows the computer time in seconds (the Matlab command cputime was used) divided by the third power of the problem size. What one expects is that all three curves, as they have the same factor preceding the $n^3$ term in the computational cost, tend to the same value for large $n$. This can be observed clearly in the figure. Moreover one can see that for computational timings the extra $n(n-1)$ operations performed by the reduction to diagonal-plus-semiseparable, w.r.t. the reduction to diagonal are negligible.

Figure 3: Computational complexity

In this last experiment we have created a symmetric matrix with eigenvalues $1,2,3,4,5$ and performed different reductions of this matrix to a diagonal-plus-semiseparable matrix, thereby varying the diagonal. The different resulting matrices are shown, and it can be seen clearly, that if an eigenvalue is present on the top left, it is revealed, by the reduction algorithm. On top the diagonal $d$ used for the reduction is shown, and below the resulting semiseparable matrix. The reader can generate much more examples indicating this convergence behavior, as the software can be downloaded. The last matrix shows that this behavior is related to the reduction algorithm as also a diagonal-plus-semiseparable matrix will be given, having as a diagonal eigenvalues in the upper left positions, but the eigenvalues are not revealed.

$$\begin{array}{c} d=[5,4,8.3812e-01,1.9640e-02,6.8128e-01] ... ...1e-01 & 4.6543e-01 & 2.7235e+00 \end{array} \right) \end{array}$$

$$\begin{array}{c} d=[1,5.0281e-01,2,3,7.0947e-01] [0.3cm] ... ...e-01 & -3.7151e-01 & 4.7934e+00 \end{array} \right) \end{array}$$

$$\begin{array}{c} d=[1,2,3,4,5] [0.3cm] S=\left(\begin{arr... ...6 & 7.2736e-16 & 2.4364e-16 & 5 \end{array} \right) \end{array}$$

This last example shows a semiseparable matrix, not coming from the reduction algorithm. Moreover it is shown that even though the diagonal contains eigenvalues of the complete diagonal-plus-semiseparable matrix in the upper left positions, they are not revealed.

$$\begin{array}{c} d=[1,2,3,8,7] [0.3cm] S=\left(\begin{arr... ...64 & -0.1352 & 1.0501 & -3.8619 \end{array} \right) \end{array}$$