The Multishift QR Algorithm. Part I: Maintaining Well-Focused Shifts and Level 3 Performance
Authors:
- Karen BramanKBKaren Braman
- Ralph ByersRBRalph Byers
- Roy MathiasRMRoy Mathias
- 1 January 2002
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 23 (4) , 929-947
Abstract
This paper presents a small-bulge multishift variation of the multishift QR algorithm that avoids the phenomenon of shift blurring, which retards convergence and limits the number of simultaneous shifts. It replaces the large diagonal bulge in the multishift QR sweep with a chain of many small bulges. The small-bulge multishift QR sweep admits nearly any number of simultaneous shifts---even hundreds---without adverse effects on the convergence rate. With enough simultaneous shifts, the small-bulge multishift QR algorithm takes advantage of the level 3 BLAS, which is a special advantage for computers with advanced architectures.Keywords
This publication has 43 references indexed in Scilit:
- The Multishift QR Algorithm. Part II: Aggressive Early DeflationSIAM Journal on Matrix Analysis and Applications, 2002
- An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblemsNumerische Mathematik, 1997
- A Simple Proof of the Transposed QR AlgorithmSIAM Review, 1996
- Convergence of the Francis shifted QR algorithm on normal matricesLinear Algebra and its Applications, 1994
- On parallelizable eigensolversAdvances in Applied Mathematics, 1992
- A Chart of Numerical Methods for Structured Eigenvalue ProblemsSIAM Journal on Matrix Analysis and Applications, 1992
- Convergence of the shifted QR algorithm on 3×3 normal matricesNumerische Mathematik, 1990
- ON A BLOCK IMPLEMENTATION OF HESSENBERG MULTISHIFT QR ITERATIONInternational Journal of High Speed Computing, 1989
- A quaternion QR algorithmNumerische Mathematik, 1989
- A Hamiltonian $QR$ AlgorithmSIAM Journal on Scientific and Statistical Computing, 1986