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

• ColPack.jl: a Julia interface to the C++ library ColPack
• SparseDiffTools.jl: contains 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.