DAG reversal is NP-complete
DAG reversal is NP-complete
复制标题
DOI：
10.1016/j.jda.2008.09.008
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
U. Naumann
中科院分区：
文献类型：
--
作者：
U. Naumann
数值计算机程序的运行可以可视化为有向无环图（dag）。对于给定的可用内存上限，我们考虑以相反顺序恢复由这样一个程序计算的中间值（DAG中的顶点）的问题。根据所执行的算术运算的数量，最小化相关的计算成本被证明是np完全的。数据流的反转可以应用，例如，在伴随数值程序的有效计算中。我们导出了需要中间值完全逆序的数值程序的特殊情况，从而建立了最优伴随计算问题的np完备性。最后但并非最不重要的是，我们回顾了一些最先进的方法，以有效的数据流反转由现有的软件工具自动微分。
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-the-art approaches to efficient data-flow reversal taken by existing software tools for automatic differentiation.