Browse Prior Art Database

AN IMPROVED SHIFT STRATEGY FOR THE QR-ALGORITHM FOR REAL HESSENBERG MATRICES

IP.com Disclosure Number: IPCOM000128311D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 10 page(s) / 27K

Publishing Venue

Software Patent Institute

Related People

Ilkka Karasalo: AUTHOR [+3]

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 text was extracted from a PDF file.
This is the abbreviated version, containing approximately 22% of the total text.

Page 1 of 10

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

Page 2 of 10

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

Page 3 of 10

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...