Deferred Shifting Schemes for Parallel QR Methods

DOI10.1137/0614016MaRDI QIDQ4033826zbMATH OpenOpenAlexFDO

Authors Robert A. van de Geijn

Publication date 16 May 1993

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0614016

zbMATH Keywords

algorithmsconvergenceeigenvaluesnumerical experimentsparallel computingQR iteration algorithmSchur decomposition

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Parallel numerical computation (65Y05)

Review text

The paper deals with shifting techniques for the QR iteration algorithm for computing the eigenvalues of dense, tridiagonal, and upper Hessenberg matrices which can be used to increase the efficiency of the implementation of these algorithms on concurrent computers. A deferred shifting strategy which allows pipelining of iterations by using ``old shifts (i.e. shifts from an iteration other than the current one) is analyzed. The theory of the convergence of algorithms of decomposition type by \textit{D. S. Watkins} and \textit{L. Elsner} [Linear Algebra Appl. 143, 19-47 (1991; Zbl 0712.65025)] is generalized to include the deferred shift. Some conditions required in these results can be relaxed. The deterioration of the convergence rate when the shift is included is discussed. The eigenvalues need not be simple to obtain quadratic convergence for nondefective nonsymmetric matrices and cubic convergence for symmetric matrices. Numerical experiments are shown as dependent on various deferring parameters.

Recommendations

• A multishift QR iteration without computation of the shifts
• The multishift QR algorithm. I: Maintaining well-focused shifts and level 3 performance
• ON A BLOCK IMPLEMENTATION OF HESSENBERG MULTISHIFT QR ITERATION
• A parallel QR algorithm for the nonsymmetric eigenvalue problem
• scientific article; zbMATH DE number 741158

Cited in

(10)

• \(QR\)-like algorithms for eigenvalue problems
• Shifting algorithms with Maple and implicit shift in the QR algorithm
• A high performance parallelization scheme for the Hessenberg double shift QR algorithm
• A shifted method for solving symmetric eigenvalue problems
• A quadratically convergent QR-like method without shifts for the Hermitian eigenvalue problem
• Algorithm 953: Parallel library software for the multishift QR algorithm with aggressive early deflation
• On deflations in extended QR algorithms
• ON A BLOCK IMPLEMENTATION OF HESSENBERG MULTISHIFT QR ITERATION
• A Wilkinson-like multishift QR algorithm for symmetric eigenvalue problems and its global convergence
• The QR steps with perfect shifts

This page was built for publication: Deferred Shifting Schemes for Parallel QR Methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4033826)