Masters Theses

Date of Award

8-1994

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Michael W. Berry

Committee Members

Micah Beck, David Straight

Abstract

In this thesis we examine sparse matrix-vector multiplication algorithms for massively- parallel computers such as the CRAY T3D. Performance results on a 256-processor CRAY T3D are presented along with a detailed analysis of each algorithm's computational complexity. The specific sparse matrix-vector multiplication algorithms discussed are the block-block algorithm (BBA) for square matrices, and the row and column block algorithms (RBA, CBA) for rectangular matrices. We also discuss the performance of these algorithms within applications, such as the Conjugate Gradient kernel from the NAS Parallel Benchmarks and a block-Lanczos method from SVD- PACK for finding the largest singular triplets of a sparse matrix. Results of this study demonstrate that the Conjugate Gradient benchmark for the class A problem size (matrix order 14,000) can be executed in 1.3 seconds which is quite competitive with published results for this benchmark on other massively-parallel machines.

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

Share

COinS