Estimating the largest singular values/vectors of large sparce matrices via modified moments

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.