SparseMatrixColorings.jl

Coloring algorithms for sparse Jacobian and Hessian matrices.

Getting started

To install this package, run the following in a Julia Pkg REPL:

pkg> add SparseMatrixColorings

Background

The algorithms implemented in this package are described in the following preprint:

• Revisiting Sparse Matrix Coloring and Bicoloring, Montoison et al. (2025)

and inspired by previous works:

• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives, Gebremedhin et al. (2005)
• New Acyclic and Star Coloring Algorithms with Application to Computing Hessians, Gebremedhin et al. (2007)
• Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation, Gebremedhin et al. (2009)
• ColPack: Software for graph coloring and related problems in scientific computing, Gebremedhin et al. (2013)

Some parts of the articles (like definitions) are thus copied verbatim in the documentation.

Alternatives

In Python:

• pysparsematrixcolorings: an experimental Python interface to the present package
• asdex: a Python-native sparse differentiation library, with coloring utilities

In Julia (unmaintained):

• ColPack.jl: a Julia interface to the C++ library ColPack
• SparseDiffTools.jl: contains older Julia implementations of some coloring algorithms

Citing

Please cite this software using the provided CITATION.cff file or the .bib entry below:

@unpublished{montoison2025revisitingsparsematrixcoloring,
      title={Revisiting Sparse Matrix Coloring and Bicoloring}, 
      author={Alexis Montoison and Guillaume Dalle and Assefaw Gebremedhin},
      year={2025},
      eprint={2505.07308},
      archivePrefix={arXiv},
      primaryClass={math.NA},
      url={https://arxiv.org/abs/2505.07308}, 
}

The link https://zenodo.org/doi/10.5281/zenodo.11314275 resolves to the latest version on Zenodo.

Contributors

<!– ALL-CONTRIBUTORS-LIST:START - Do not remove or modify this section –> <!– prettier-ignore-start –> <!– markdownlint-disable –> <table> <tbody> <tr> <td align="center" valign="top" width="14.28%"><a href="https://github.com/amontoison"><img src="https://avatars.githubusercontent.com/u/35051714?v=4?s=100" width="100px;" alt="Alexis Montoison"/><br />_{<b>Alexis Montoison</b>}</a><br /><a href="#ideas-amontoison" title="Ideas, Planning, & Feedback">🤔</a> <a href="#code-amontoison" title="Code">💻</a> <a href="#doc-amontoison" title="Documentation">📖</a> <a href="#maintenance-amontoison" title="Maintenance">🚧</a> <a href="#research-amontoison" title="Research">🔬</a> <a href="#review-amontoison" title="Reviewed Pull Requests">👀</a> <a href="#talk-amontoison" title="Talks">📢</a></td> <td align="center" valign="top" width="14.28%"><a href="https://gdalle.github.io/"><img src="https://avatars.githubusercontent.com/u/22795598?v=4?s=100" width="100px;" alt="Guillaume Dalle"/><br />_{<b>Guillaume Dalle</b>}</a><br /><a href="#ideas-gdalle" title="Ideas, Planning, & Feedback">🤔</a> <a href="#code-gdalle" title="Code">💻</a> <a href="#doc-gdalle" title="Documentation">📖</a> <a href="#maintenance-gdalle" title="Maintenance">🚧</a> <a href="#research-gdalle" title="Research">🔬</a> <a href="#review-gdalle" title="Reviewed Pull Requests">👀</a> <a href="#talk-gdalle" title="Talks">📢</a></td> </tr> </tbody> </table>

<!– markdownlint-restore –> <!– prettier-ignore-end –>

<!– ALL-CONTRIBUTORS-LIST:END –>