Multiprocessor sparse SVD algorithms and applications

In this thesis, we develop four numerical methods for computing the singular value decomposition (SVD) of large sparse matrices on a multiprocessor architecture. We particularly consider the SVD of unstructured sparse matrices in which the number of rows may be substantially larger or smaller than the number of columns. On vector machines, considerable progress has been made over the past 10 years in developing robust algorithms for the solution of the sparse symmetric eigenvalue problem using Lanczos (with or without re-orthogonalization) and subspace iteration methods. Our intent is to extend and refine this knowledge for computing the sparse singular value decomposition on a parallel computer. We emphasize Lanczos, block-Lanczos, subspace iteration, and trace minimization methods for determining several of the largest (or smallest) singular triplets (singular values and corresponding left- and right-singular vectors) for sparse matrices arising from certain practical applications. The target architectures for implementations of such methods include the Alliant FX/80 and the Cray-2S/4128. This algorithmic research is particularly motivated by recent information-retrieval techniques in which high-rank approximations to large sparse term-document matrices are needed, and by nonlinear inverse problems arising from seismic reflection tomography applications.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Berry, Michael Waitsel

Contributors dc:contributor

• Sameh, Ahmed H.

• Computer Science

Statement dc:rights

• Copyright 1991 Berry, Michael Waitsel

Language dc:language

eng

Identifier

AAI9124383
(UMI)AAI9124383

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/19563