Deferred Shifting Schemes for Parallel QR Method
- Robert A. van de Geijn
- Department of Computer Sciences
- University of Texas
- Austin, TX 78712
Abstract
Parallel implementation of the QR algorithm for
solving the symmetric eigenvalue problem requires more than a
straight-forward 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, we
generalize the theory of the convergence of algorithms of
decomposition type for the algebraic eigenvalue problem developed by
Watkins and Elsner. We extend their results to deferred shifting
schemes, which allow pipelining of iterations in parallel
implementations, and analyze the deterioration of the convergence
rate. Furthermore, we show that eigenvalues need not be simple in
order to obtain quadratic convergence for nondefective nonsymmetric
matrices and cubic convergence for symmetric matrices.
Robert van de Geijn,
``Deferred Shifting Schemes for Parallel QR Methods,''
in SIAM Journal on Matrix Analysis and Application,
14, 1, pp. 180-194, Jan. 1993.