Implicit QR with compression

DOI10.1016/J.INDAG.2012.05.006MaRDI QIDQ692576zbMATH OpenOpenAlexFDO

Authors Paola Boito, L. Gemignani, I. Gohberg, Y. Eidelman

Publication date 6 December 2012

Published in Indagationes Mathematicae. New Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.indag.2012.05.006

zbMATH Keywords

algorithmbackward stabilitycompanion matrixeigenvalue computationHessenberg matricesnumerical experimentspolynomial rootsQR methodquasiseparable matrices

Mathematics Subject Classification ID

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

Review text

In some earlier papers the implicit shifted QR-algorithm was introduced and discussed in particular for companion matrices. This method is based on the observation that Hessenberg matrices of the form \(U - pq^T\) where \(U\) is a unitary Hessenberg matrix and \(p,q\) are of rank 1 keep this form under the QR-algorithm. Thus one has an algorithm for finding the roots of a polynomial of degree \(n\) using only \(O(n)\) storage and \(O(n^2)\) flops. In this paper, such an algorithm given in an earlier paper is further simplified and thus speeded up. Extensive numerical experiments are reported which show backward stability, though this property could not yet be proved.

Recommendations

• A fast implicit QR eigenvalue algorithm for companion matrices
• Implicit Shifting in the QR and Related Algorithms
• scientific article; zbMATH DE number 24380
• scientific article; zbMATH DE number 4001318
• The QR Algorithm Revisited

Cites work

• A fast implicit QR eigenvalue algorithm for companion matrices
• A fast QR algorithm for companion matrices
• Fast QR Eigenvalue Algorithms for Hessenberg Matrices Which Are Rank‐One Perturbations of Unitary Matrices
• scientific article; zbMATH DE number 5527834 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• Implicit double shift \(QR\)-algorithm for companion matrices
• Numerical recipes. The art of scientific computing.
• On the shifted QR iteration applied to companion matrices
• The QR algorithm: 50 years later its genesis by John Francis and Vera Kublanovskaya and subsequent developments

Cited in

(10)

• Fast QR iterations for unitary plus low rank matrices
• Fast computation of eigenvalues of companion, comrade, and related matrices
• Implicit QR for rank-structured matrix pencils
• Implicit QR for companion-like pencils
• Matrix structures in queuing models
• Fast and backward stable computation of roots of polynomials. II: Backward error analysis; companion matrix and companion pencil
• Implicit Shifting in the QR and Related Algorithms
• Fast and Backward Stable Computation of Roots of Polynomials
• A CMV-Based Eigensolver for Companion Matrices
• Implicit double shift \(QR\)-algorithm for companion matrices

This page was built for publication: Implicit QR with compression

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