Efficient Computation of Sparse Hessians:
An Experimental Study Using ADOL-C

Abstract.

Interior-point methods require second-order derivatives of the Lagrangian function, and exact Hessians are needed in parametric sensitivity analysis. A Hessian can be computed accurately using automatic differentiation (AD). When the sparsity structure of the Hessian is known, the computation can be made efficient using the following three-steps procedure. First, obtain a seed matrix S that defines a column partition of the Hessian H via a specialized graph coloring. Second, compute the numerical values of the entries of the compressed Hessian B=HS using AD. Third, recover the numerical values of the entries of the original matrix H from the compressed representation B. The coloring variant used in the first step depends on whether the recovery in the third step is direct or substitution-based: a direct method uses star coloring whereas a substitution 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. In this paper we provide a detailed description of the recovery routines, 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. The obtained results show that sparsity exploitation via coloring renders enormous savings in runtime and makes the computation of Hessians of very large size feasible. The results also show that evaluating a Hessian via a substitution method using acyclic coloring is faster than a direct evaluation using star coloring---and the speedup is achieved without compromising numerical accuracy.

Key words.  sparse Hessian computation; acyclic coloring; star coloring; automatic differentiation; combinatorial scientific computing.