|
Efficient computation of sparse Hessians
using coloring and Automatic Differentiation
Abstract.
The computation of a sparse Hessian matrix $H$ using
automatic differentiation (AD) can be made efficient using
the following four-step procedure.
- Determine the sparsity structure of $H$.
- Obtain a seed matrix $S$ that defines
a column partition of $H$
using a specialized coloring on the adjacency graph of $H$.
- Compute the compressed Hessian matrix $B=HS$.
- Recover the numerical values of the entries of $H$ from $B$.
The coloring variant used in the second step depends on whether the
recovery in the fourth step is direct or indirect:
a direct method uses star coloring, and an indirect method uses
acyclic coloring. In an earlier work, we had designed and
implemented effective heuristic algorithms for these two NP-hard
coloring problems. Recently, we integrated part of the developed
software with the AD tool ADOL-C, which has recently acquired a
sparsity detection capability.
In this paper, we provide a detailed
description and analysis of the recovery algorithms, and
experimentally demonstrate the efficacy of the coloring techniques in
the overall process of computing the Hessian of a given function using
ADOL-C as an example of an AD tool. We also present new analytical
results on star and acyclic coloring of chordal graphs. The
experimental results show that sparsity exploitation via coloring
yields enormous savings in runtime and makes the computation of
Hessians of very large size feasible. The results also show that
evaluating a Hessian via an indirect method is often faster than a
direct evaluation. This speedup is achieved without compromising
numerical accuracy.
|
|
