Optimal matrix distribution by simulated annealing for a parallel sparse matrix-vector multiplication

Abstract

In parallel Sparse Matrix-Vector Multiplication (SpMV), finding an efficient matrix partitioning is crucial to minimize communication cost. This thesis explores the use of Simulated Annealing to find optimal matrix bipartitions. The method uses row/column-based moves to explore the possible partitioning solutions.

Our findings indicate that the introduced method is promising for bipartitioning large sparse matrices, especially when exact algorithms prove to be computationally expensive.