Browse Prior Art Database

Block Lanczos Eigenelement Algorithm

IP.com Disclosure Number: IPCOM000082722D
Original Publication Date: 1975-Jan-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 3 page(s) / 67K

Publishing Venue

IBM

Related People

Cullum, JK: AUTHOR [+2]

Abstract

In the computation of eigenelements (eigenvalues and eigenvectors) of a matrix, it is often necessary to compute only a few extreme (algebraically largest or smallest) eigenvalues and a basis for a corresponding eigenspace. For small matrices (n<100) a routine may be used that computes all the eigenelements. However, for large matrices, matrices for which n(n+1)/2 double precision numbers will not fit into the high-speed store of the computer, these procedures are infeasible.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Block Lanczos Eigenelement Algorithm

In the computation of eigenelements (eigenvalues and eigenvectors) of a matrix, it is often necessary to compute only a few extreme (algebraically largest or smallest) eigenvalues and a basis for a corresponding eigenspace. For small matrices (n<100) a routine may be used that computes all the eigenelements. However, for large matrices, matrices for which n(n+1)/2 double precision numbers will not fit into the high-speed store of the computer, these procedures are infeasible.

The present algorithm comprises a method for computing iteratively, q extreme eigenelements of a large sparse symmetric matrix A of order n (q<<n) without altering A. Similar block algorithms in use utilize heuristically generated shifts of A, and thus convergence to the desired eigenelements cannot be assured. Moreover, the original Lanczos method which uses a single vector [blocks of size 1] encounters numerical difficulties, unless the vectors generated are continuously reorthogonalized with respect to all vectors previously generated. Furthermore, it can generate at most 1 eigenvector from the invariant subspace of each distinct eigenvalue. Therefore, it cannot easily identify and compute a complete set of eigenvectors for an eigenvalue of multiplicity >1.

Block Lanczos eigenelement algorithm (BLAN) works with blocks of size greater than or equal to the number of eigenelements desired.

Subspace convergence is obtained (not necessarily convergence to individual eigenvectors); so there are no difficulties with multiple eigenvalues. The shifts used in BLAN are computed automatically and the eigenvalues converge monotonically to the desired eigenvalues. Zero eigenvalues and eigenvalues nearly equal in magnitude, but opposite in sign, are handled directly. For a more detailed description of the BLAN algorithm, please see the IBM Research Center Report RC 4845, May 14, 1974.

The flow chart indicates the basic steps in the BLAN algorithm. Professor W. Kahan of the Department of EE and CS at the University of California at Berkeley, suggested the basic Block Lanczos procedure. The mixed precision computation used in computing the second block at each iteration was also his suggestion. The essential points of this description are the following.

(1) Whenever a vector in P(1) is dropped either because of convergence or dependence, the blocks P(j) j>3 subsequently generated are each reorthogonalized with respect to each progenitor in Q(1) of a vector in P(1) that has been dropped. (see Equation 3.8 in RC 4845). This reorthogonalization is necessary (see Examples 3.1 and 3.2 in RC 4845), because when a vector is dropped from P it indicates that that vector is `zero' but, of course, it is only zero to something less than single precision. With this reorthogonalization, it can be proved (see...