A GPU-based Approximate SVD Algorithm
Department of Computer Science, University of Massachusetts, Amherst, MA 01003, USA
9th International Conference on Parallel Processing and Applied Mathematics, 2011
@article{foster2011gpu,
title={A GPU-based Approximate SVD Algorithm},
author={Foster, B. and Mahadevan, S. and Wang, R.},
year={2011}
}
Approximation of matrices using the Singular Value Decomposition (SVD) plays a central role in many science and engineering applications. However, the computation cost of an exact SVD is prohibitively high for very large matrices. In this paper, we describe a GPU-based approximate 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 describe how to map QUIC-SVD onto the GPU, and improve its speed and stability using a blocked Gram-Schmidt orthogonalization method. 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. Using 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.
December 15, 2011 by hgpu
