Hybrid seminar at GERAD and on Zoom.

The matrices of first and second derivatives that drive numerical optimization, the Jacobian of the constraints and the Hessian of the Lagrangian, are rarely dense. In a large problem each constraint touches only a few of the variables, and a Newton or interior-point method will ask for both matrices at every iteration. Automatic sparse differentiation (ASD) leverages that structure in four stages: find the sparsity pattern, color it, differentiate in compressed form, then decompress. This talk walks through all four, with the emphasis on coloring.

Where does the pattern come from? From running AD on a different arithmetic. Instead of propagating numbers, propagate the answer to the question "which inputs does this quantity depend on?", with addition and multiplication replaced by OR and AND. A single run of the program then reveals the whole pattern. What it costs depends on how each intermediate quantity stores its list of dependencies: either the list of relevant integer indices, compact but scattered in memory, or one bit per input, wasteful but very fast to combine.

Coloring is where the real combinatorics lives, and the idea behind it is simple. If two columns of a Jacobian have no nonzeros in common, one AD pass can recover both at once, because their entries cannot collide. Grouping as many columns as possible is then a graph coloring problem. Coloring columns suits forward mode and coloring rows suits reverse mode. Symmetry lets Hessians do better still, through star or acyclic coloring. And recent work on bicoloring shows how to use both directions at once, which pays off when a matrix has dense rows and dense columns together.

Further reading: An Illustrated Guide to Automatic Sparse Differentiation