Distributed-memory Algorithms for Sparse Matrix Permutation, Extraction, and Assignment
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914056036679680 |
|---|---|
| author | Hassani, Elaheh Hussain, Md Taufique Azad, Ariful |
| author_facet | Hassani, Elaheh Hussain, Md Taufique Azad, Ariful |
| contents | We present scalable distributed-memory algorithms for sparse matrix permutation, extraction, and assignment. Our methods follow an Identify-Exchange-Build (IEB) strategy where each process identifies the local nonzeros to be sent, exchanges the required data, and then builds its local submatrix from the received elements. This approach reduces communication compared to SpGEMM-based methods in distributed memory. By employing synchronization-free multithreaded algorithms, we further accelerate local computations, achieving substantially better performance than existing libraries such as CombBLAS and PETSc. We design efficient software for these operations and evaluate their performance on two university clusters and the Perlmutter supercomputer. Our experiments span a variety of application scenarios, including matrix permutation for load balancing, matrix reordering, subgraph extraction, and streaming graph applications. In all cases, we compare our algorithms against CombBLAS, the most comprehensive distributed library for these operations, and, in some scenarios, against PETSc. Overall, this work provides a comprehensive study of algorithms, software implementations, experimental evaluations, and applications for sparse matrix permutation, extraction, and assignment. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_20776 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Distributed-memory Algorithms for Sparse Matrix Permutation, Extraction, and Assignment Hassani, Elaheh Hussain, Md Taufique Azad, Ariful Distributed, Parallel, and Cluster Computing Mathematical Software G.4 We present scalable distributed-memory algorithms for sparse matrix permutation, extraction, and assignment. Our methods follow an Identify-Exchange-Build (IEB) strategy where each process identifies the local nonzeros to be sent, exchanges the required data, and then builds its local submatrix from the received elements. This approach reduces communication compared to SpGEMM-based methods in distributed memory. By employing synchronization-free multithreaded algorithms, we further accelerate local computations, achieving substantially better performance than existing libraries such as CombBLAS and PETSc. We design efficient software for these operations and evaluate their performance on two university clusters and the Perlmutter supercomputer. Our experiments span a variety of application scenarios, including matrix permutation for load balancing, matrix reordering, subgraph extraction, and streaming graph applications. In all cases, we compare our algorithms against CombBLAS, the most comprehensive distributed library for these operations, and, in some scenarios, against PETSc. Overall, this work provides a comprehensive study of algorithms, software implementations, experimental evaluations, and applications for sparse matrix permutation, extraction, and assignment. |
| title | Distributed-memory Algorithms for Sparse Matrix Permutation, Extraction, and Assignment |
| topic | Distributed, Parallel, and Cluster Computing Mathematical Software G.4 |
| url | https://arxiv.org/abs/2509.20776 |