Efficient computation of eigenvalues of randomly generated matrices

摘要

Recently, Geist has given an algorithm to find eigenvalues of a general matrix by tridiagonalization, followed by L lower triangular, R upper triangle (LR) iteration. The total computational cost is 43n3+ O(n2) flops. This paper shows how to modify Geist's approach to produce a banded Hessenberg form and employs Rayleigh coefficient iteration to refine the eigenvalues obtained from LR iteration. These techniques appear to significantly improve the accuracy of the computation without greatly increasing the computational cost. Results of numerical experiments on randomly generated matrices are given. The proposed algorithm appears to be have significantly better potential for parallelization than the standard method of reduction to Hessenberg form followed by implicit Q orthogonal, R upper triangular (QR) iteration.