The Divide-and-Conquer Method for the Solution of the Symmetric Tridiagonal Eigenproblem and Transputer Implementations

This thesis describes a divide-and-conquer method for solving the symmetric tridiagonal eigenproblem and its parallel implementation on a transputer network. The method was first developed by Cuppen based on previous ideas of Bunch et al. who showed how to compute the eigensystem of a diagonal matrix which is perturbed by a rank-one matrix.

We develop a new approach to the theory for arriving at the secular equation, the roots of which are the eigenvalues of a given symmetric tridiagonal matrix. We present new proofs for the convergence of the iterative method which finds these roots. We incorporate into the solution process an alternative way of computing any root when it is found to be very close to the right endpoint of the interval, generated from data for the unperturbed matrix, within which it is located. When this situation occurs the computation of the corresponding eigenvector is obstructed. Our reformulation circumvents this difficulty and, used in conjunction with the original means of computing the roots, produces generally more accurate results.

We have implemented the Divide-and-Conquer algorithm on a network of transputers organized in a rectangular grid. This organization works well, while remaining straight-forward to program. Because of the way the Divide-and-Conquer method works, our implementation is best suited to a number of processors which is a power of two. The maximum number of transputers for which the program was tested was 16.

The Divide-and-Conquer method was found to be faster than the QL algorithm, even when executed in sequential mode. An explanation for this is suggested by complexity models, which we have developed. The method was also found to have good scalability when the number of processors is increased; that is we still obtain good speed-up values when more processors are used. A further feature is its super linearity performance: efficiencies greater than 1 have been obtained. To some extent our complexity model explains this; it does not, however, take into account communication issues, which will be the subject of future work.