Journal of Combinatorics

Volume 14 (2023)

Number 4

Hessian chain bracketing

Pages: 539 – 558

DOI: https://dx.doi.org/10.4310/JOC.2023.v14.n4.a7

Authors

Uwe Naumann (Department of Computer Science, RWTH Aachen University, Aachen, Germany)

Shubhaditya Burela (Department of Computer Science, RWTH Aachen University, Aachen, Germany)

Abstract

Second derivatives of mathematical models for real-world phenomena are fundamental ingredients of a wide range of numerical simulation methods including parameter sensitivity analysis, uncertainty quantification, nonlinear optimization and model calibration. The evaluation of such Hessians often dominates the overall computational effort. The combinatorial Hessian Accumulation problem aiming to minimize the number of floating-point operations required for the computation of a Hessian turns out to be NP‑complete. We propose a dynamic programming formulation for the solution of Hessian Accumulation over a sub-search space. This approach yields improvements by factors of ten and higher over the state of the art based on second-order tangent and adjoint algorithmic differentiation.

Keywords

chain rule of differentiation, algorithmic differentiation, Hessian, NP-completeness, dynamic programming

2010 Mathematics Subject Classification

Primary 65D25, 90C39. Secondary 90C60.

Received 26 October 2021

Published 14 April 2023