9th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems

Iterative Randomized Algorithms for Low Rank Approximation of Terascale Matrices with Small Spectral Gaps

Authors: Chander J. Iyer (Rensselaer Polytechnic Institute, Yahoo! Research)

Abstract: Randomized approaches for low rank matrix approximations have become popular in recent years and often offer significant advantages over classical algorithms because of their scalability and numerical robustness on distributed memory platforms. We present a distributed implementation of randomized block iterative methods to compute low rank matrix approximations for dense tera-scale matrices. We are particularly interested in the behavior of randomized block iterative methods on matrices with small spectral gaps. Our distributed implementation is based on four iterative algorithms: block subspace iteration, the block Lanczos method, the block Lanczos method with explicit restarts, and the thick-restarted block Lanczos method. We analyze the scalability and numerical stability of the four block iterative methods and demonstrate the performance of these methods for various choices of the spectral gap. Performance studies demonstrate superior runtimes of the block Lanczos algorithms over the subspace power iteration approach on (up to) 16,384 cores of AMOS, Rensselaer's IBM Blue Gene/Q supercomputer.

Archive Materials


Back to 9th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems Archive Listing

Back to Full Workshop Archive Listing