Revisiting Sparse Matrix Coloring and Bicoloring
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915283404324864 |
|---|---|
| author | Montoison, Alexis Dalle, Guillaume Gebremedhin, Assefaw |
| author_facet | Montoison, Alexis Dalle, Guillaume Gebremedhin, Assefaw |
| contents | Sparse matrix coloring and bicoloring are fundamental building blocks of sparse automatic differentiation. Bicoloring is particularly advantageous for rectangular Jacobian matrices with at least one dense row and column. Indeed, in such cases, unidirectional row or column coloring demands a number of colors equal to the number of rows or columns. We introduce a new strategy for bicoloring that encompasses both direct and substitution-based decompression approaches. Our method reformulates the two variants of bicoloring as star and acyclic colorings of an augmented symmetric matrix. We extend the concept of neutral colors, previously exclusive to bicoloring, to symmetric colorings, and we propose a post-processing routine that neutralizes colors to further reduce the overall color count. We also present the Julia package SparseMatrixColorings, which includes these new bicoloring algorithms alongside all standard coloring methods for sparse derivative matrix computation. Compared to ColPack, the Julia package also offers enhanced implementations for star and acyclic coloring, vertex ordering, as well as decompression. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_07308 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Revisiting Sparse Matrix Coloring and Bicoloring Montoison, Alexis Dalle, Guillaume Gebremedhin, Assefaw Numerical Analysis Discrete Mathematics Mathematical Software Combinatorics 05C15 (Primary), 65F50, 65D25, 68R10, 90C06 (Secondary) Sparse matrix coloring and bicoloring are fundamental building blocks of sparse automatic differentiation. Bicoloring is particularly advantageous for rectangular Jacobian matrices with at least one dense row and column. Indeed, in such cases, unidirectional row or column coloring demands a number of colors equal to the number of rows or columns. We introduce a new strategy for bicoloring that encompasses both direct and substitution-based decompression approaches. Our method reformulates the two variants of bicoloring as star and acyclic colorings of an augmented symmetric matrix. We extend the concept of neutral colors, previously exclusive to bicoloring, to symmetric colorings, and we propose a post-processing routine that neutralizes colors to further reduce the overall color count. We also present the Julia package SparseMatrixColorings, which includes these new bicoloring algorithms alongside all standard coloring methods for sparse derivative matrix computation. Compared to ColPack, the Julia package also offers enhanced implementations for star and acyclic coloring, vertex ordering, as well as decompression. |
| title | Revisiting Sparse Matrix Coloring and Bicoloring |
| topic | Numerical Analysis Discrete Mathematics Mathematical Software Combinatorics 05C15 (Primary), 65F50, 65D25, 68R10, 90C06 (Secondary) |
| url | https://arxiv.org/abs/2505.07308 |