A multishift QR iteration without computation of the shifts

DOI10.1007/BF02140681MaRDI QIDQ1334239zbMATH OpenFDO

Authors A. A. Dubrulle, Gene H. Golub

Publication date 2 May 1995

Published in Numerical Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02140681

zbMATH Keywords

characteristic polynomialconvergenceeigenvaluesgeneralized eigenproblemHessenberg matrixmultishift QR iterationQR algorithmshift vector

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Review text

This paper introduces an algorithm that produces the shift vector for multishift QR from the evaluation of the characteristic polynomial of a Hessenberg matrix, thus avoiding the computation of eigenvalues of the trailing principal submatrix of order \(m\) (the number of shifts of the origin of the spectrum in each step required to control convergence) of the iterated matrix, as it is necessary in the multishift QR iteration by \textit{Z. Bai} and \textit{J. Demmel} [Int. J. High Speed Comput. 1, No. 1, 97-112 (1989; Zbl 0726.65035)]. The present algorithm is stable, more accurate, faster, and simpler than the other. It is a matrix extension of \textit{M. A. Hyman's} method [Eigenvalues and eigenvectors of general matrices. 12th ACM National Meeting, Houston, TX (1957)]. Experiments to confirm those claims were done on an HP 9000/720 work- station (IEEE double precision) for Hessenberg matrices with entries uniformly distributed on \((-1,1)\) and for orthogonally Hessenberg-reduced matrices with entries distributed as before, typically for runs between \(n= 100\) and 300 steps and \(m\leq n/2\). The improvement on time of a QR eigenvalue solver was relatively modest. The new scheme extends to the generalized eigenproblem.

Recommendations

• ON A BLOCK IMPLEMENTATION OF HESSENBERG MULTISHIFT QR ITERATION
• Efficient Implementation of the Multishift QR Algorithm for the Unitary Eigenvalue Problem
• Implicit Shifting in the QR and Related Algorithms
• The QR Algorithm Revisited
• The transmission of shifts and shift blurring in the QR algorithm
• A note on the double-shift \(QL\) algorithm
• Fast and stable unitary QR algorithm
• scientific article; zbMATH DE number 1097561
• Fast QR Eigenvalue Algorithms for Hessenberg Matrices Which Are Rank‐One Perturbations of Unitary Matrices
• The periodic QR algorithm is a disguised QR algorithm

Cites work

• An Algorithm for Generalized Matrix Eigenvalue Problems
• Convergence of algorithms of decomposition type for the eigenvalue problem
• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 781814 (Why is no real title available?)
• scientific article; zbMATH DE number 3349178 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• scientific article; zbMATH DE number 3109835 (Why is no real title available?)
• Laguerre's Method Applied to the Matrix Eigenvalue Problem
• Matrix eigensystem routines - EISPACK guide. 2nd ed
• ON A BLOCK IMPLEMENTATION OF HESSENBERG MULTISHIFT QR ITERATION
• The QR Transformation A Unitary Analogue to the LR Transformation--Part 1

Cited in

(22)

• Hyman's method revisited
• Computation of a few small eigenvalues of a large matrix with application to liquid crystal modeling
• A QR algorithm with variable iteration multiplicity
• Shifting algorithms with Maple and implicit shift in the QR algorithm
• On swapping diagonal blocks in real Schur form
• A quadratically convergent QR-like method without shifts for the Hermitian eigenvalue problem
• The multishift QR algorithm. I: Maintaining well-focused shifts and level 3 performance
• The multishift QR algorithm. II: Aggressive early deflation
• scientific article; zbMATH DE number 3881772 (Why is no real title available?)
• ON A BLOCK IMPLEMENTATION OF HESSENBERG MULTISHIFT QR ITERATION
• Origin-shifted algorithm for matrix eigenvalues
• Deferred Shifting Schemes for Parallel QR Methods
• scientific article; zbMATH DE number 741158 (Why is no real title available?)
• The QR steps with perfect shifts
• Numerical solution of linear eigenvalue problems
• scientific article; zbMATH DE number 4001318 (Why is no real title available?)
• A generalization of the multishift QR algorithm
• Implicit Shifting in the QR and Related Algorithms
• Efficient Implementation of the Multishift QR Algorithm for the Unitary Eigenvalue Problem
• Numerical Analysis and Its Applications
• The convergence of multi-shift QR algorithm for symmetric matrices
• Rational QR-iteration without inversion

Describes a project that uses

Uses Software

• CLAPACK
• LAPACK
• EISPACK

This page was built for publication: A multishift QR iteration without computation of the shifts

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