Discrete Applied Mathematics Seminar by Alexis Montoison: Revisiting Coloring and Bicoloring for Sparse Automatic Differentiation

Speaker: Alexis Montoison, research scientist, Argonne National Laboratory

 

Title: Revisiting Coloring and Bicoloring for Sparse Automatic Differentiation

 

Coloring and bicoloring are fundamental building blocks of sparse automatic differentiation and play a key role in the efficient computation of sparse Jacobians and Hessians for nonlinear optimization solvers.

Bicoloring is particularly advantageous for rectangular Jacobian matrices that contain at least one dense row and one dense column. In such situations, traditional unidirectional row or column colorings typically require as many colors as there are rows or columns. We introduce a new bicoloring strategy that encompasses both direct and substitution-based decompression approaches.

 

Our method reformulates these two bicoloring variants as star and acyclic colorings of an augmented symmetric matrix, enabling the reuse of algorithms and software components originally developed for Hessian computations.

In addition, we extend the concept of neutral colors, previously restricted to bicoloring, to symmetric colorings, and we propose an inexpensive post-processing routine that neutralizes colors to further reduce the overall number of colors, and thus the number of required directional derivatives. Finally, we present the Julia package SparseMatrixColorings.jl, which implements these new bicoloring strategies alongside standard coloring methods for sparse derivative matrix computation.

 

 

Discrete Applied Math Seminar