A DIVIDE-AND-CONQUER ALGORITHM FOR THE SYMMETRICAL TRIDIAGONAL EIGENPROBLEM

The authors present a stable and efficient divide-and-conquer algorithm for computing the spectral decomposition of an N x N symmetric tridiagonal matrix. The key elements are a new, stable method for finding the spectral decomposition of a symmetric arrowhead matrix and a new implementation of deflation. Numerical results show that this algorithm is competitive with bisection with inverse iteration, Cuppen's divide-and-conquer algorithm, and the QR algorithm for solving the symmetric tridiagonal eigenproblem.