Sequential and data-parallel implementations of a Lanczos algorithm for the singular value decomposition

In this thesis, we present both sequential and data-parallel implementations of the single-vector Lanczos algorithm for computing the singular value decomposition of large unstructured sparse matrices. Our intent is to produce robust numerical software in C that is portable across a variety of high-performance workstations such as the IBM RS/6000, DEC 5000-200, Sun Sparcstation 2, and Apple Macintosh Ilfx. Furthermore, this software should be easily incorporated into larger application programs such as those from large-scale information retrieval applications which require the computation of singular values and singular vectors of sparse matrices. Using the MasPar Programming Language on the MasPar MP-1 computer system, we develop a systematic approach for redesigning our software for a data-parallel environment. We approximate several of the largest singular values and singular vectors of a test suite of sparse matrices using two different equivalent eigensystems and provide benchmark and performance comparisions for each machine considered.