A multishift QR iteration without computation of the shifts

Each iteration of the multishift QR algorithm of Bai and Demmel requires the computation of a shift vector defined bym shifts of the origin of the spectrum that control the convergence of the process. A common choice of shifts consists of the eigenvalues of the trailing principal submatrix of orderm, 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.The work of this author was in part supported by the National Science Foundation, grant number ESC-9003107, and the Army Research Office, grant number DAAL-03-91-G-0038.