Parallelizing the Approximate Minimum Degree Ordering Algorithm: Strategies and Evaluation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914350504083456 |
|---|---|
| author | Chang, Yen-Hsiang Buluç, Aydın Demmel, James |
| author_facet | Chang, Yen-Hsiang Buluç, Aydın Demmel, James |
| contents | The approximate minimum degree algorithm is widely used before numerical factorization to reduce fill-in for sparse matrices. While considerable attention has been given to the numerical factorization process, less focus has been placed on parallelizing the approximate minimum degree algorithm itself. In this paper, we explore different parallelization strategies, and introduce a novel parallel framework that leverages multiple elimination on distance-2 independent sets. Our evaluation shows that parallelism within individual elimination steps is limited due to low computational workload and significant memory contention. In contrast, our proposed framework overcomes these challenges by parallelizing the work across elimination steps. To the best of our knowledge, our implementation is the first scalable shared memory implementation of the approximate minimum degree algorithm. Experimental results show that we achieve up to a 7.29x speedup using 64 threads over the state-of-the-art sequential implementation in SuiteSparse. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17097 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parallelizing the Approximate Minimum Degree Ordering Algorithm: Strategies and Evaluation Chang, Yen-Hsiang Buluç, Aydın Demmel, James Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms The approximate minimum degree algorithm is widely used before numerical factorization to reduce fill-in for sparse matrices. While considerable attention has been given to the numerical factorization process, less focus has been placed on parallelizing the approximate minimum degree algorithm itself. In this paper, we explore different parallelization strategies, and introduce a novel parallel framework that leverages multiple elimination on distance-2 independent sets. Our evaluation shows that parallelism within individual elimination steps is limited due to low computational workload and significant memory contention. In contrast, our proposed framework overcomes these challenges by parallelizing the work across elimination steps. To the best of our knowledge, our implementation is the first scalable shared memory implementation of the approximate minimum degree algorithm. Experimental results show that we achieve up to a 7.29x speedup using 64 threads over the state-of-the-art sequential implementation in SuiteSparse. |
| title | Parallelizing the Approximate Minimum Degree Ordering Algorithm: Strategies and Evaluation |
| topic | Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.17097 |