SILO: Automatic Sparse Differentiation: Exploiting Structure in Jacobians and Hessians

Abstract

Newton and interior-point methods ask, at every iteration, for two derivative matrices: the Jacobian of the constraints and the Hessian of the Lagrangian. Automatic differentiation (AD) can produce both from nothing more than a program that evaluates the functions. But AD does not return a matrix. It returns an operator, one matrix-vector product at a time. A full Jacobian in R^(m x n) therefore costs n forward passes or m reverse passes, which is hopeless in high dimension.

Unless the matrix is sparse, which it nearly always is: each constraint touches only a few of the variables. Automatic sparse differentiation (ASD) exploits that structure in four stages: detect the sparsity pattern, color it, differentiate in compressed form, then decompress. This talk walks through all four, assuming only a limited AD background, with the emphasis on coloring.

The pattern itself comes from running AD on a different arithmetic: propagate “which inputs does this quantity depend on?” instead of numbers, and a single run of the program reveals the whole structure. Coloring is where the combinatorics lives, since columns that share no row can be recovered in one pass, which turns n passes into a handful. Symmetry lets Hessians do better still. I will then turn to bicoloring, which uses forward and reverse mode together and is the only option when a matrix has both dense rows and dense columns, and show that it is a special case of symmetric coloring, so that a single implementation covers both problems.

Further reading: An Illustrated Guide to Automatic Sparse Differentiation
Note: The research associated with this presentation was conducted at Argonne National Laboratory.

Bio

Alexis Montoison is a senior member of technical staff at AMD and a member of the rocSPARSE team. He was previously a postdoctoral researcher in the Mathematics and Computer Science division at Argonne National Laboratory. His work covers high-performance algorithms for sparse linear algebra, continuous optimization, and automatic differentiation, with an emphasis on portability across CPUs and GPUs. He is the principal developer of Krylov.jl and libHSL. He holds a Ph.D. in applied mathematics from Polytechnique Montréal.