# zbMATH — the first resource for mathematics

Optimal Jacobian accumulation is NP-complete. (English) Zbl 1158.68013
Summary: We show that the problem of accumulating Jacobian matrices by using a minimal number of floating-point operations is NP-complete by reduction from ensemble computation. The proof makes use of the fact that, deviating from the state-of-the-art assumption, algebraic dependences can exist between the local partial derivatives. It follows immediately that the same problem for directional derivatives, adjoints, and higher derivatives is NP-complete, too.

##### MSC:
 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 65D25 Numerical differentiation
##### Keywords:
automatic differentiation; complexity; NP-completeness