Parallelizing the computation of eigenvalues for real symmetric tridiagonal matrices

Finding eigenvalues of a real symmetric tridiagonal matrix T is one of the important numerical problems in scientific computing. Some important numerical algorithms require the computation of only one eigenvalue for large real symmetric tridiagonal matrices. The dissertation presents a modified parallel algorithm for computing one eigenvalue of T based on the parallel bisection scheme [1]. A proposed scaling method is used to prevent the overflow and underflow problems suffered by the parallel scheme in [1]. It is formally shown that the scaling method is valid in preventing the overflow and underflow problems. The modified parallel algorithm is implemented on the nCUBE-2 hypercube. Numerical tests show that the parallel algorithm achieves significant speedup and comparable accuracy over the sequential bisection method.; As the second result in the dissertation, a parallel modified multisection algorithm for computing all eigenvalues of T is developed. A new splitting strategy is proposed to isolate eigenvalues into subintervals in the isolation phase. It is shown that the new splitting strategy is significantly more efficient than that of the conventional parallel multisection algorithms. The Laguerre iteration with the cubic convergence rate is used to extract eigenvalues in the extraction phase of the parallel algorithm. In the implementation of the parallel algorithm on nCUBE-2, a dynamic task scheduling method is developed to solve the load balancing problem. Numerical results show that the parallel modified multisection algorithm achieves considerably high speedup and superior accuracy over the conventional parallel multisection algorithm.; A parallel split-merge algorithm for computing all eigenvalues of T is developed as the third result of the dissertation. The split-merge algorithm uses the Laguerre iteration to extract eigenvalues. The similar dynamic task scheduling method is used in the implementation of the parallel split-merge algorithm on nCUBE-2. Numerical tests show that the parallel split-merge algorithm achieves significant speedup and superior accuracy over the conventional parallel multisection algorithm. The performance comparison between the parallel modified multisection algorithm and the parallel split-merge algorithm shows that the parallel modified multisection is significantly faster while both parallel algorithms have the same good accuracy.