ON TRIDIAGONALIZING AND DIAGONALIZING SYMMETRICAL MATRICES WITH REPEATED EIGENVALUES

We describe a divide-and-conquer tridiagonalization approach for matri ces with repeated eigenvalues. Our algorithm hinges on the fact that, under easily constructively verifiable conditions, a symmetric matrix with band width b and k distinct eigenvalues must be block diagonal wi th diagonal blocks of size at most bk. A slight modification of the us ual orthogonal band-reduction algorithm allows us to reveal this struc ture, which then leads to potential parallelism in the form of indepen dent diagonal blocks. Compared to the usual Householder reduction algo rithm, the new approach exhibits improved data locality, significantly more scope for parallelism, and the potential to reduce arithmetic co mplexity by close to 50% for matrices that have only two numerically d istinct eigenvalues. The actual improvement depends to a large extent on the number of distinct eigenvalues and a good estimate thereof. How ever, at worst the algorithms behave like a successive band-reduction approach to tridiagonalization. Moreover, we provide a numerically rel iable and effective algorithm for computing the eigenvalue decompositi on of a symmetric matrix with two numerically distinct eigenvalues. Su ch matrices arise, for example, in invariant subspace decomposition ap proaches to the symmetric eigenvalue problem.