Efficient Parallel Access Patterns for Sparse Matrices

A notable characteristic of the scientific computing and machine learning prob-lem domains is the large amount of data to be analyzed and manipulated. Here, carefully crafted parallel algorithms have the potential to make a massive impact on the size of a problem that is deemed tractable. Sparse matrices are a data struc-ture frequently encountered within these domains. Typically, these sparse matri-ces have a non-uniform structure, which can make the task of designing efficient parallel algorithms for sparse matrices much more complex than for their dense counterparts. In this report, we consider multiple ways of parallelizing the most computationally intensive section of a typical sparse matrix algorithm — its inner loop. We compare the theoretical trade-offs between each of the approaches and empirically test performance on the Netflix Prize data set [4, 5], a large collabora-tive filtering task that seeks to learn movie preferences from a sparse collection of ratings.