Chasing Algorithms for the Eigenvalue Problem

A generic chasing algorithm for the matrix eigenvalue problem is introduced and studied. This algorithm includes, as special cases, the implicit, multiple-step $QR$ and $LR$ algorithms and similar bulge-chasing algorithms for the standard eigenvalue problem. The scope of the generic chasing algorithm is quite broad; it encompasses a number of chasing algorithms that cannot be analyzed by the traditional (e.g., implicit Q theorem) approach. These include the $LR$ algorithm with partial pivoting and other chasing algorithms that employ pivoting for stability, as well as hybrid algorithms that combine elements of the $LR$ and $QR$ algorithms. The main result is that each step of the generic chasing algorithm amounts to one step of the generic $GR$ algorithm. Therefore the convergence theorems for $GR$ algorithms that were proven in a previous work [D. S. Watkins and L. Elsner, Linear Algebra Appl., 143 (1991), pp. 19–47] also apply to the generic chasing algorithm.