A multishift QR iteration without computation of the shifts (Q1334239): Difference between revisions
From MaRDI portal
Changed an Item |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: CLAPACK / rank | |||
Normal rank |
Revision as of 01:06, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A multishift QR iteration without computation of the shifts |
scientific article |
Statements
A multishift QR iteration without computation of the shifts (English)
0 references
2 May 1995
0 references
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.
0 references
QR algorithm
0 references
shift vector
0 references
characteristic polynomial
0 references
Hessenberg matrix
0 references
eigenvalues
0 references
convergence
0 references
multishift QR iteration
0 references
generalized eigenproblem
0 references