HP Labs Technical Reports

A Multishift QR Iteration without Computation of the Shifts

Dubrulle, Augustin A.; Golub, Gene H.

HPL-93-54

Keyword(s):

Abstract: Each iteration of the multishift QR algorithm of Bai and Demmel requires the computation of a "shift vector" defined by "m" shifts of the origin of the spectrum, which control the convergence of the process. A common choice of shifts consists of the eigenvalues of the trailing principal submatrix of order "m", and current practice includes the computation of these eigenvalues in the determination of the shift vector. In this paper, we describe an algorithm based on the evaluation of the characteristic polynomial of a Hessenberg matrix, which directly produces the shift vector without computing eigenvalues. This algorithm is stable, more accurate, faster, and simpler than the current alternative. It also allows for a consistent shift strategy with dynamic adjustment of the number of shifts.

Back to Index