Title: Efficient Algorithms for Band Reduction and Sparse SVD

Speaker: Siva Rajamanickam, University of Florida

Date/Time: Tuesday, November 10, 2009 at 9:00 – 10:00 am        

Location: CSRI Building, Room 90 (Sandia NM)

Brief Abstract: 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 talk, we consider the singular value decomposition problem for band and sparse matrices, especially the bidiagonal reduction of band and sparse matrices.

I will introduce blocked algorithms for 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. The algorithms use pipelined plane rotations to restrict the fill to a scalar, utilize the cache correctly and perform better than competing methods in terms of the amount of required workspace. Our band reduction methods are several times faster than existing methods.

I will also introduce the theory and algorithms for direct method for sparse singular value decomposition. 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. 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 iterative methods. It performs much faster than existing methods when more singular values are required.

CSRI POC: Mike Heroux, (320) 845-7695