Hypergraph partitioning based models and methods for exploiting cache locality in sparse matrix-vector multiplication (Q2847753)

The authors investigate single and multiple sparse matrix-vector multiplications (SpMxV). For single SpMxV, they propose two cache-size-aware row/column reordering methods based on one-dimensional (1D) and two-dimensional (2D) top-down sparse matrix partitioning. They make use of the column-net hypergraph model for the 1D method and enhance the row-column-net hypergraph model for the 2D method. The authors evaluate performances of the proposed models and methods on a wide range of sparse matrices. They point out that the proposed methods outperform the available schemes, and that the methods based on 2D partitioning perform better than 1D partitioning methods.