The ELR Method for Computing the Eigenvalues of a General Matrix
Achiya Dax, Shmuel Kaniel · SIAM Journal on Numerical Analysis · 1981
This paper presents an algorithm for computing all the eigenvalues of a full nonsymmetric matrix A. All the current algorithms begin with the reduction of A to a Hessenberg matrix H. It is widely believed that the QR algorithm is the best method for computing the eigenvalues of H. In this paper we suggest an alternative method which based on the fact that the eigenvalues of a tridiagonal matrix can be computed much faster than those of a Hessenberg matrix. We first reduce H to a tridiagonal matrix T and then compute the eigenvalues of T. The reduction of H to T is performed by the elimination method [3], while the eigenvalues of T are computed by the LR method. Although the above two methods have been well known for a long time, their use in this way has traditionally been rejected because of the possibility of numerical instability. We show here that under certain conditions the elimination method is quite stable. Furthermore, we describe a strategy for the LR algorithm that, again, results in stability. The new method and the QR method can be combined effectively. It is suggested that the QR algorithm be used only in the few cases where the stability of the new algorithm cannot be ensured. Our experience with the algorithm demonstrates that it requires only 17 percent of the QR algorithm’s computation time. Numerical experiments are included.