A GPU-based approximate SVD algorithm

Abstract. Approximation of matrices using the Singular Value Decom-position (SVD) plays a central role in many science and engineering appli-cations. However, the computation cost of an exact SVD is prohibitively high for very large matrices. In this paper, we describe a GPU-based ap-proximate SVD algorithm for large matrices. Our method is based on the QUIC-SVD introduced by [6], which exploits a tree-based structure to efficiently discover a subset of rows that spans the matrix space. We de-scribe how to map QUIC-SVD onto the GPU, and improve its speed and stability using a blocked Gram-Schmidt orthogonalization method. Us-ing a simple matrix partitioning scheme, we have extended our algorithm to out-of-core computation, suitable for very large matrices that exceed the main memory size. Results show that our GPU algorithm achieves 6∼7 times speedup over an optimized CPU version of QUIC-SVD, which itself is orders of magnitude faster than exact SVD methods