DAG reversal is NP-complete
| Autor: | Uwe Naumann |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Discrete mathematics
business.industry Automatic differentiation Computation Data-flow reversal Adjoint code Upper and lower bounds NP-completeness Theoretical Computer Science Reverse order Software Computational Theory and Mathematics Discrete Mathematics and Combinatorics Minification NP-complete business Algorithm Mathematics |
| Zdroj: | Journal of Discrete Algorithms. 7(4):402-410 |
| ISSN: | 1570-8667 |
| DOI: | 10.1016/j.jda.2008.09.008 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect