Iterative sparse matrix partitioning

Abstract

At the core of many numerical methods lies one simple operation: the sparse matrix-vector multiplication. Because the systems involved are usually of large size, to speed up this computation we partition the matrix, dividing the work among different processors. This division requires communication between these processors, which has to be minimized. The goal of the thesis was to come up with different strategies to be used with the medium-grain method, to build an iterative framework that re-uses information on the current partitioning to lower the communication volume; furthermore, we tried to apply the same concepts to obtain a better initial partitioning of a matrix.