Browse Prior Art Database

An Accelerated Bisection Method for the Calculation of Eigenvalues of a .- Symmetric Tridiagonal Matrix

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

Publishing Venue

Software Patent Institute

Related People

Herbert J. Bernstein: AUTHOR [+3]

Abstract

When a modest subset of the eigenvalues of a symmetric tridiagonal matrix is required, the most effective technique available is the bisection method presented by Givens [4,5]. As Wilkinson [6] notes, once an eigenvalue is approximately located, final convergence by interpolation may be more economical than continued bisection. However, in the case of repeated or clustered eigenvalues, interpolation is likely to be more expensive than bisection. Distinguishing the isolated eigenvalues from the repeated ones can often require more code and time than completion of the bisection. Indeed, many obvious techniques for converging to eigenvalues faster than with bisection turn out to take fewer steps, but considerably more time, because so much more has to be done in the inner loop. Further,

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 14% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

An Accelerated Bisection Method for the Calculation of Eigenvalues of a
.- Symmetric Tridiagonal Matrix

by Herbert J. Bernstein*

Technical Report No. 79 July 1983 *Permanent address: Chemistry Department, Brookhaven National Laboratory, Upton, New York An Accelerated Bisection Method for the Calculation of Eigenvalues of a Symmetric Tridiagonal Matrix

Herbert J. Bernstein*

Summary.

We present a method for the determination of eigenvalues of a symmetric tridiagonal matrix which combines Givens' Sturm bisection [4,5] with interpolation, to accelerate convergence in high precision cases. By using an appropriate root of the absolute value of the determinant to derive the interpolation weight, results are obtained which compare favorably with the Berth, Martin, Wilkinson algorithm [1].

Subject Classifications: AMS(MOS): 15A18,15-04,65F10; CR: 5.14

1. Introduction

When a modest subset of the eigenvalues of a symmetric tridiagonal matrix is required, the most effective technique available is the bisection method presented by Givens [4,5]. As Wilkinson [6] notes, once an eigenvalue is approximately located, final convergence by interpolation may be more economical than continued bisection. However, in the case of repeated or clustered eigenvalues, interpolation is likely to be more expensive than bisection. Distinguishing the isolated eigenvalues from the repeated ones can often require more code and time than completion of the bisection. Indeed, many obvious techniques for converging to eigenvalues faster than with bisection turn out to take fewer steps, but considerably more time, because so much more has to be done in the inner loop. Further,

Courant Institute of Mathematical Sciences, New York University, New York, New York 10012. Permanent Address: Chemistry Department, Brookhaven National Laboratory, Upton, New York 11973. Bernstein: Accelerated Bisection Page-2

when calculations to near the limiting accuracy of the machine used are required, bisection has the distinct advantage of avoiding convergence questions.

We can retain the guaranteed convergence of bisection by using interpolation only to suggest a new division point, and can solve the problem of repeated eigenvalues by using the appropriate root of the determinant as a weight. This requires us to carry the unsealed determinant value in some form, which is a small change in the orginal bisection technique [4,5]. In those cases where high accuracy is required and the matrix is large this approach provides a significant

New York University Page 1 Dec 31, 1983

Page 2 of 10

An Accelerated Bisection Method for the Calculation of Eigenvalues of a .- Symmetric Tridiagonal Matrix

improvement in computing time as compared to the original bisection technique. However, on machines where high precision division is not very expensive compared to multiplication, the revised bisection technique of Barth, Martin and Wilkinson...