Doctoral Dissertations

Date of Award

12-1995

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Computer Science

Major Professor

Michael W. Berry

Committee Members

Jack Dongarra, Jens Gergor, Tse-wei Wang, Gene Golub

Abstract

This dissertation considers algorithms for determining a few of the largest singular values and corresponding vectors of large sparse matrices by solving equivalent eigen- value problems. The procedure is based on a method by Golub and Kent for estimating eigenvalues of equivalent eigensystems using modified moments. The asynchronicity in the computations of moments and eigenvalues makes this method attractive for parallel implementations on a network of workstations. However, one potential drawback to this method is that there is no obvious relationship between the modified moments and the eigenvectors. The lack of eigenvector approximations makes deflation schemes difficult, and no robust implementation of the Golub/Kent scheme are currently used in practical applications. Methods to approximate both eigenvalues and eigenvectors using the theory of modified moments in conjunction with the Chebyshev semi-iterative method are described in this dissertation. Deflation issues and implicit error approximation methods are addressed to present a complete algorithm. The performance of an ANSI-C implementation of this scheme on a network of UNIX workstations using PVM is presented. The portability of this implementation is demonstrated through results on a 256 processor Cray T3D massively-parallel computer.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS