View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Beyond bipartitioning: Exact sparse matrix partitioning into multiple parts.

        Thumbnail
        View/Open
        Master_thesis_Final.pdf (1.006Mb)
        Publication date
        2021
        Author
        Jenneskens, Lieneke
        Metadata
        Show full item record
        Summary
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/272
        Collections
        • Theses

        Related items

        Showing items related by title, author, creator and subject.

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

          Noordam, Pieter (2025)
          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 ...
        • Iterative sparse matrix partitioning 

          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 ...
        • Self-Improving Sparse Matrix Partitioning and Bulk-Synchronous Pseudo-Streaming 

          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 ...
        Utrecht university logo