Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributor.advisorBisseling, Rob
dc.contributor.authorJenneskens, Lieneke
dc.date.accessioned2021-12-08T00:00:16Z
dc.date.available2021-12-08T00:00:16Z
dc.date.issued2021
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/272
dc.description.abstractMatrix-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.
dc.description.sponsorshipUtrecht University
dc.language.isoEN
dc.subjectIn 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 developed 2 different methods to solve the sparse matrix partitioning problem; one is based on the branch and bound method, the other method is based on ILP.
dc.titleBeyond bipartitioning: Exact sparse matrix partitioning into multiple parts.
dc.type.contentMaster Thesis
dc.rights.accessrightsOpen Access
dc.subject.keywordsmatrix partitioning; branch and bound; ILP; recursive bipartitioning
dc.subject.courseuuMathematical Sciences
dc.thesis.id1133


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record