Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

# GENERALIZED RAYLEIGH METHODS WITH APPLICATIONS TO FINDING EIGENVALUES OF LARGE MATRICES

IP.com Disclosure Number: IPCOM000128497D
Original Publication Date: 1970-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 14 page(s) / 35K

## Publishing Venue

Software Patent Institute

## Related People

James S. Vandergraft: AUTHOR [+3]

## Abstract

Since the development of the Sturm sequence method [10] and, later, the QR algorithm [2], the computational problem of finding the eigenvalues and eigenvectors of a symmetric matrix A is essentially solved provided A is not too large. In both of these methods, the matrix is first reduced to tri-diagonal form. If A is extremely large, this preliminary reduction may not be computationally reasible for several reasons. First of all, it requires the use of the entire matrix in a series of transformations and no use can be made of sparseness or bandedness of two characteristics of most large matrices which occur in applications. Secondly, if only a few eigenvalues and eigenvectors are required (as is usually the case), the reduction may take more time than is reasonable. Finally, it often happens that physical considerations can provide rough approximations to some of the eigenvalues or eigenvectors. The above mentioned methods cannot make much use of such inforemation. In [4], I. Erdelyi proposed a method for finding p eigenvalues and eigenvecttors of an [Equation ommitted] matrix A, where n is large and [Equation ommitted]. An important feature of this method is that the only operation which involves the matrix A itself is matrix vector multiplication. Hence, A can be stored on magnetic tape (or other auxilliary storage) and sparseness and bandedness can be taken into account to reduce the amount of computation. A major drawback, however, is the necessity of finding the roots of a polynomial of degreee p; a difficult problem for even moderate sizes of p. n this paper, we present a theory of generalized Rayleigh quotients which can be used to develop methods, such as Erdelyi's, for calculating some of the eigenvalues and eigenvectors of large matrices. If X is an approximation to an eigenvector of a [Equation ommitted] symmetric matrix A, then the Rayleigh Quotient (1.1) [Equation ommitted] is an approximation to an eigenvalue of A. Our generalization of this concept involves the construction of a [Equation ommitted] matrix B, where usually [Equation ommitted]. The eigenvalues are, in fact, Rayleigh quotients of A corresponding to certain approximate eigenvectors which are determined by the eigenvectors of B. The matrix B is obtained by restricting A to a p dimensional subspace H. If H is invariant under A, then the eigenvalues of B are also eigenvalues of A. In general, of course, H will not be invariant, and the accuracy of the appxoximations will depend on how "nearly" invariant H. is. This leads to the problem of constructing subspaces which are nearly invariant, and the related problem of estimating how close a subspace is to being invariant. The problem of constructing invariant subspaces can be solved using Bauer's Treppeniteration [1] or the method of Collar and Jahn [3]. (See [8] for a description of these techniques). Both of these methods, however, employ a series of trasnsformations which use the entire matrix A and hence suffer from the same disadvantages, for large matrices, as does the reduction to tri-diagonal form.

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

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

GENERALIZED RAYLEIGH METHODS WITH APPLICATIONS TO FINDING EIGENVALUES OF LARGE MATRICES

James S. Vandergraft

This research was supported in part by the National Aeronautics and Space Administration under Grant NGL-21-002-008 to the Computer Science center of the University of Maryland.

Section 1. Introduction

Since the development of the Sturm sequence method [10] and, later, the QR algorithm [2], the computational problem of finding the eigenvalues and eigenvectors of a symmetric matrix A is essentially solved provided A is not too large. In both of these methods, the matrix is first reduced to tri-diagonal form. If A is extremely large, this preliminary reduction may not be computationally reasible for several reasons. First of all, it requires the use of the entire matrix in a series of transformations and no use can be made of sparseness or bandedness of two characteristics of most large matrices which occur in applications. Secondly, if only a few eigenvalues and eigenvectors are required (as is usually the case), the reduction may take more time than is reasonable. Finally, it often happens that physical considerations can provide rough approximations to some of the eigenvalues or eigenvectors. The above mentioned methods cannot make much use of such inforemation.

In [4], I. Erdelyi proposed a method for finding p eigenvalues and eigenvecttors of an

(Equation Omitted)

matrix A, where n is large and

(Equation Omitted)

. An important feature of this method is that the only operation which involves the matrix A itself is matrix vector multiplication. Hence, A can be stored on magnetic tape (or other auxilliary storage) and sparseness and bandedness can be taken into account to reduce the amount of computation. A major drawback, however, is the necessity of finding the roots of a polynomial of degreee p; a difficult problem for even moderate sizes of p. n this paper, we present a theory of generalized Rayleigh quotients which can be used to develop methods, such as Erdelyi's, for calculating some of the eigenvalues and eigenvectors of large matrices. If X is an approximation to an eigenvector of a

(Equation Omitted)

symmetric matrix A, then the Rayleigh Quotient

(1.1)

(Equation Omitted)

University of Maryland Page 1 Dec 31, 1970

Page 2 of 14

GENERALIZED RAYLEIGH METHODS WITH APPLICATIONS TO FINDING EIGENVALUES OF LARGE MATRICES

is an approximation to an eigenvalue of A. Our generalization of this concept involves the construction of a

(Equation Omitted)

matrix B, where usually

(Equation Omitted)

. The eigenvalues are, in fact, Rayleigh quotients of A corresponding to certain approximate eigenvectors which are determined by the eigenvectors of B. The matrix B is obtained by restricting A to a p dimensional subspace H. If H is invariant under A, then the eigenvalues of B are also eigenvalues of A. In general, of course, H will not be invariant, and the accuracy of th...