Journal of Combinatorics
Volume 14 (2023)
Hessian chain bracketing
Pages: 539 – 558
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.
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