GLOBAL CONVERGENCE OF HESSENBERG SHIFTED QR II: FINITE ARITHMETIC

We develop a framework for proving rapid convergence of shifted QR algorithms which use Ritz values as shifts, in finite precision arithmetic. Our key contribution is a dichotomy result which addreses the known forward-instability issues surrounding the shifted QR iteration [B. N. Parlett and J. Le, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 279-316]: we give a procedure which provably either computes a set of approximate Ritz values of a Hessenberg matrix with good forward stability properties or leads to early decoupling of the matrix via a small number of QR steps. Using this framework, we show that the shifting strategy of [J. Banks, J. Garza-Vargas, and N. Srivastava, Global Convergence of Hessenberg Shifted QR I: Dynamics, arXiv:2111.07976, 2022] converges rapidly in finite arithmetic with a polylogarithmic bound on the number of bits of precision required, when invoked on matrices of controlled eigenvector condition number and minimum eigenvalue gap.