Beyond bipartitioning: Exact sparse matrix partitioning into multiple parts.
MetadataShow full item record
Matrix-vector multiplications appear in many algorithms, and in many cases the matrices used in these multiplications are sparse. The time needed for the matrix-vector multiplication computation can be decreased by performing the multiplication in parallel. In order to minimize the communication in parallel sparse matrix-vector 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 NP-Complete. 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.
Showing items related by title, author, creator and subject.
Taviani, D. (2013)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 ...
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 ...
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 matrix-vector multiplication (SpMV) can be sped up ...