The BR eigenvalue algorithm

The BR algorithm, a new method for calculating the eigenvalues of an upper Hessenberg matrix, is introduced. It is a bulge-chasing algorithm like the QR algorithm, but, unlike the QR algorithm, it is well adapted to computing the eigenvalues of the narrow-band, nearly tridiagonal matrices generated by the look-ahead Lanczos process. This paper describes the BR algorithm an d gives numerical evidence that it works well in conjunction with the Lancz os process. On the biggest problems run so far, the BR algorithm beats the QR algorithm by a factor of 30-60 in computing time and a factor of over 10 0 in matrix storage space.