Implicit Shifting in the QR and Related Algorithms

Abstract

A new approach is suggested for deriving the theory of implicit shifting in the QR algorithm applied to a Hessenberg matrix. This is less concise than Francis’ original approach ([Comput. J., 4(1961), pp. 265–271], [Comput. J., 4(1962), pp. 332–345]) but is more instructive, and extends easily to more general cases. For example, it enables us to design implicitly shifted QR algorithms for band and block Hessenberg matrices. It can also be applied to related algorithms such as the LR algorithm, and to algorithms which do not produce triangular matrices in the factorization step. The approach provides details that can be useful in designing numerically effective algorithms in various areas. In addition to the above, the standard theory describing the result of the QR algorithm with k shifts on a Hessenberg matrix A is extended to the case where some of the shifts can be eigenvalues. This has a practical value in special cases such as eigenvalue allocation. The extension is given for both the explicitly and implicitly shifted QR algorithms, and shows to what extent the latter mimics the former. The new approach to the theory again handles the implicit case simply and clearly.