Efficient algorithms for sparse singular value decomposition

Singular value decomposition is a problem that is used in a wide variety of applications like latent semantic indexing, collaborative filtering and gene expression analysis. In this study, we consider the singular value decomposition problem for band and sparse matrices. Linear algebraic algorithms for modern computer architectures are designed to extract maximum performance by exploiting modern memory hierarchies, even though this can sometimes lead to algorithms with higher memory requirements and more floating point operations. We propose blocked algorithms for sparse and band bidiagonal reduction.;The blocked algorithms are designed to exploit the memory hierarchy, but they perform nearly the same number of floating point operations as the non-blocked algorithms. We introduce efficient blocked band reduction algorithms that utilize the cache correctly and perform better than competing methods in terms of the number of floating point operations and the amount of required workspace. Our band reduction methods are several times faster than existing methods.;The theory and algorithms for sparse singular value decomposition, especially algorithms for reducing a sparse upper triangular matrix to a bidiagonal matrix are proposed here. The bidiagonal reduction algorithms use a dynamic blocking method to reduce more than one entry at a time. They limit the sub-diagonal fill to one scalar by pipelining the blocked plane rotations. A symbolic factorization algorithm for computing the time and memory requirements for the bidiagonal reduction of a sparse matrix helps the numerical reduction step.;Our sparse singular value decomposition algorithm computes all the singular values at the same amount of time it takes to compute a few singular values using existing methods. It performs much faster than existing methods when more singular values are required. The features of the software implementing the band and sparse bidiagonal reduction algorithms are also presented. (Full text of this dissertation may be available via the University of Florida Libraries web site. Please check http://www.uflib.ufl.edu/etd.html)...