On optimality preserving eliminations for the minimum edge count and optimal Jacobian accumulation problems in linearized DAGs

Abstract

The minimum edge count (MEC) and optimal Jacobian accumulation problems in linearized directed acyclic graphs (DAGs) result from the combinatorics induced by the associativity of the chain rule of differential calculus. This paper discusses a suitable graph formalism followed by proving a number of results that yield a considerable search space reduction for both problems. An algorithmic link between numerical analysis and theoretical computer science is established. Although both problems are believed to be NP-hard in general, a linear-time algorithm is presented solving the MEC problem for a specified subclass of l-DAGs.

Keywords:

• linearized DAG
• minimal edge count
• edge elimination
• vertex elimination
• scarcity

AMS Subject Classification :

• 05C85
• 05C50

Acknowledgements

Viktor Mosenkis is supported by DFG grant No. 487/2-1: ‘Combinatorial Aspects of Derivative Computation’. The authors wish to acknowledge several fruitful discussions with Andrew Lyons and Jean Utke at the Argonne National Laboratory's Mathematics and Computer Science Division.