AN IMPROVED SHIFT STRATEGY FOR THE QR-ALGORITHM FOR REAL HESSENBERG MATRICES
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Publishing Venue
Software Patent Institute
Related People
Ilkka Karasalo: AUTHOR [+2]
Abstract
We present some experimental results on the behavior of the QR-algorithm for real Hesse.nberg matrices,.with shifts c~lculated from a px p lower right-hand sub.matrix where p may be > 2. We show how one such shiftin&strategy may be conveniently implemented in a programming language permitting recursive procedure calls by modifying slightly the ALGOL procedure HQR by Martin, Peters and Wilkinson [1]. In our comparison-the modified procedure gives in general a 15- 20% reduction of the total operations count for transforming the Hessenberg matrix to block triangular form (with diagonal blocks of order < 2) and updating the productof the orthogonal transformation matrices. Work performed under the auspices of the U.S. Energy Research and Development Administration -2-
THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.
AN IMPROVED SHIFT STRATEGY FOR THE QR-ALGORITHM FOR REAL HESSENBERG MATRICES
Ilkka Karasalo
Lawrence Berkeley Laboratory University of California Berkeley, California 94720
January 1976
ABSTRACT
We present some experimental results on the behavior of the QR-algorithm for real Hesse.nberg matrices,.with shifts c~lculated from a px p lower right-hand sub.matrix where p may be > 2. We show how one such shiftin&strategy may be conveniently implemented in a programming language permitting recursive procedure calls by modifying slightly the ALGOL procedure HQR by Martin, Peters and Wilkinson [1]. In our comparison-the modified procedure gives in general a 15- 20% reduction of the total operations count for transforming the Hessenberg matrix to block triangular form (with diagonal blocks of order < 2) and updating the productof the orthogonal transformation matrices.
Work performed under the auspices of the U.S. Energy Research and Development Administration -2-
1. INTRODUCTION
The shifted QR-algorithm by Francis [71 is perhaps the most effective and reliable general- purpose procedure for the matrix eigen-value problem
(Equation Omitted)
Here A is a real n x n matrix, x EE R , and X is a scalar. The algorithm is described by the following formulas
(Equation Omitted)
where the
(Equation Omitted)
are unitary and upper triangular
matrices,, respectively, and
(Equation Omitted)
University of California at Berkeley Page 1 Dec 31, 1976
AN IMPROVED SHIFT STRATEGY FOR THE QR-ALGORITHM FOR REAL HESSENBERG MATRICES
are the scalar shifts of origin. It is easily seen from (1.2) that if A 0 A is an upper Hessenberg matrix, then so is
(Equation Omitted)
For economy of computation, therefore, in practicethe original matrix of (1.1) is reduced to upper Hessenberg form before entering the algorithm (1.2).
When
(Equation Omitted)
rather mild necessary and-sufficient conditions may be found (Parlett [61) for the convergence of A s as s-*- to a block-triangular matrix with diagonal blocks of order < 2. The rate of thisconvergence (which is in general linear) may be drastically improved by choosing k S appropriate
(Equation Omitted)
In fact, if
(Equation Omitted)
is an eigenvalue of
(Equation Omitted)
and further if
(Equation Omitted)
where both X and X are eigenvalues of
(Equation Omitted)
then
(Equation Omitted)
and the bottom ee diagonal block of A has
(Equation Omitted)
-3-
the eigenvalues
In practice, of course, the eigenvalues of A are not known in advance. In implementations (see e.g.,[11) the shifts are commonly chosen
University of California at Berkeley Page 2 Dec 31, 1976
AN IMPROVED SHIFT STRATEGY FOR THE QR-ALGORITHM FOR REAL HESSENBERG MATRICES
to be the two eigenvalues of the bottom 2X 2 diagonal block of A (strategy s A for futurereference), and the QR-steps are performed using the implicit double-shift idea of Francis [4, p.525]. Other shifting strate...