Structural Optimal Jacobian Accumulation and Minimum Edge Count are NP-Complete Under Vertex Elimination

Matthias Bentert, Alex Crane, Pål Grønås Drange +2

We study graph-theoretic formulations of two fundamental problems in algorithmic differentiation. The first (Structural Optimal Jacobian Accumulation) is that of computing a Jacobi…