Optimizing sparse matrix kernels for data mining

Many data mining algorithms rely on eigenvalue computations or iterative linear solvers in which the running time is dominated by sparse matrix-vector products. Sparse matrix-vector multiplication on modern machines often runs one to two orders of magnitude slower than peak hardware performance, and because of their lack of structure, the worst performance is often observed for matrices from text retrieval and other data mining applications. In this paper we explore a set of memory hierarchy optimizations for sparse matrix-vector multiplication, concentrating on matrices that arises in text and image retrieval. We also consider algorithms that multiply the sparse matrix by a set of vectors, and show that reorganizing the code to take advantage of multiple vectors can significantly speed up the running time. These optimization are supported by a code generation and optimization system called Sparsity, which automatically tunes sparse matrix-vector multiplication for a given matrix structure and machine.