Journal
INFORMS JOURNAL ON COMPUTING
Volume 21, Issue 2, Pages 209-223Publisher
INFORMS
DOI: 10.1287/ijoc.1080.0286
Keywords
sparse Hessian computation; acyclic coloring; star coloring; automatic differentiation; combinatorial scientific computing
Categories
Funding
- U. S. Department of Energy [DE-FC-0206-ER-25774]
- U. S. National Science Foundation [ACI 0203722]
- German Research Foundation [Wa 1607/2-1]
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [0830645] Funding Source: National Science Foundation
Ask authors/readers for more resources
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 equivalent to 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available