On Optimal DAG Reversal
Uwe Naumann
Runs of numerical computer programs can be visualized as directed acyclic
graphs (DAGs). We consider the problem of restoring the intermediate
values computed by such a program (the vertices in the DAG) in reverse
order for a given upper bound on the available memory. The minimization
of the associated computational cost in terms of the number of performed
arithmetic operations is shown to be NP-complete. The reversal of the
data-flow finds application, for example, in the efficient evaluation
of adjoint numerical programs. We derive special cases of numerical
programs that require the intermediate values exactly in reverse order,
thus establishing the NP-completeness of the optimal adjoint computation
problem. Last but not least we review some state-of-theart approaches
to efficient data-flow reversal taken by existing software tools for
automatic differentiation.