Beyond bipartitioning: Exact sparse matrix partitioning into multiple parts.
Summary
Matrixvector multiplications appear in many algorithms, and in many cases the matrices used in these multiplications are sparse. The time needed for the matrixvector multiplication computation can be decreased by performing the multiplication in parallel. In order to minimize the communication in parallel sparse matrixvector multiplications, we need to solve the sparse matrix partitioning problem, that is the partitioning of a sparse matrix A into p disjoint parts, while minimizing the communication volume. This problem is NPComplete.
We present an algorithm based on the branch and bound method which optimally partitions a matrix into p disjoint parts, for the general case of p is greater than or equal to 2. We also present an integer linear programming model which solves the sparse matrix partitioning problem.
We used the results found by these exact methods for p=4 to analyse the performance of recursive bipartitioning. The results show that the recursive bipartitioning method performs very well.
Collections
Related items
Showing items related by title, author, creator and subject.

Iterative sparse matrix partitioning
Taviani, D. (2013)At the core of many numerical methods lies one simple operation: the sparse matrixvector multiplication. Because the systems involved are usually of large size, to speed up this computation we partition the matrix, dividing ... 
Cache optimization for sparse matrixvector multiplication
Mulder, P.J. (2015)In this thesis we introduce a cost measure to compare the cache friendliness of different permutations of the rows and columns of a given matrix. And we implement a simple algorithm that tries to reorder the rows and ... 
SelfImproving Sparse Matrix Partitioning and BulkSynchronous PseudoStreaming
Buurlage, J. (2016)One of the backbone operations in numerical mathematics is multiplying a sparse matrix with a vector. In computations involving very large linear systems, the sparse matrixvector multiplication (SpMV) can be sped up ...