Deferred Shifting Schemes for Parallel QR Methods
Robert A. Geijn · SIAM Journal on Matrix Analysis and Applications · 1993
Parallel implementation of the QR algorithm for solving the symmetric eigenvalue problem requires more than a straightforward transcription of sequential code to parallel code. Experimental adjustments include new shifting techniques and omission of the initial reducing to upper Hessenberg form. In this paper, the theory of the convergence of algorithms of decomposition type for the algebraic eigenvalue problem developed by Watkins and Elsner is generalized. The results are extended to deferred shifting schemes, which allow pipelining of iterations in parallel implementations, and analyzing the deterioration of the convergence rate. Furthermore, it is shown that eigenvalues need not be simple to obtain quadratic convergence for nondefective nonsymmetric matrices and cubic convergence for symmetric matrices.