A New Class of Fast Divide-and-Conquer Algorithms for the Real Symmetric Tridiagonal Eigenvalue Problem

The computation of the eigenvalues and orthogonal eigenvectors of an N x N real symmetric tridiagonal matrix is a well known problem in numerical analysis. The problem frequently arises in the determination of eigenvalues and eigenvectors of dense and banded symmetric matrices and in connection with various families of orthogonal polynomials and special functions satisfying three term recurrence relations. Numerous algorithms exist for the solution of this problem, which typically require O(N2) operations for the determination of eigenvalues and O(N3) operations for the determination of orthogonal eigenvectors.;In this thesis we propose a new class of fast algorithms for the computation of the eigenvalues of a symmetric tridiagonal matrix in O( N ln N) operations. Such an algorithm may be combined with any one of the existing methods for the determination of eigenvectors of a symmetric tridiagonal matrix with known eigenvalues. The underlying technique is a divide-and-conquer approach which determines eigenvalues of a larger tridiagonal matrix from those of constituent matrices by the use of relations of their characteristic polynomials. The evaluation of characteristic polynomials is accelerated by the use of a technique known as the Fast Multipole Method. We provide a detailed presentation of a prototype for this class of algorithms and discuss several generalizations.;An implementation of a prototype for this class of algorithms has been developed in FORTRAN, which serves to provide a comparison with existing techniques in terms of running time and accuracy. We present numerical results which demonstrate the effectiveness of the method.