Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation

• Published in: INFORMS journal on computing 2009-03, Vol.21 (2), p.209-223
• Main Authors: Gebremedhin, Assefaw H, Tarafdar, Arijit, Pothen, Alex, Walther, Andrea
• Format: Article
• Language: English
• Subjects: acyclic coloring; Algorithms; automatic differentiation; Automation; combinatorial scientific computing; Differences; Evaluation; Heuristic; Mathematical optimization; Matrices; Matrix; Scientific method; sparse Hessian computation; Sparsity; star coloring; Studies
• ISSN: 1091-9856; 1526-5528; 1091-9856
• DOI: 10.1287/ijoc.1080.0286

The computation of a sparse Hessian matrix H using automatic differentiation (AD) can be made efficient using the following four-step procedure: (1) Determine the sparsity structure of H , (2) obtain a seed matrix S that defines a column partition of H using a specialized coloring on the adjacency graph of H , (3) compute the compressed Hessian matrix B HS , and (4) 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.